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 838099712 : bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
79 : {
80 838099712 : bitmap_obstack *bit_obstack = head->obstack;
81 :
82 838099712 : if (GATHER_STATISTICS)
83 : release_overhead (head, sizeof (bitmap_element), false);
84 :
85 838099712 : elt->next = NULL;
86 838099712 : elt->indx = -1;
87 838099712 : if (bit_obstack)
88 : {
89 834851122 : elt->prev = bit_obstack->elements;
90 834851122 : bit_obstack->elements = elt;
91 : }
92 : else
93 : {
94 3248590 : elt->prev = bitmap_ggc_free;
95 3248590 : 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 13759462079 : bitmap_element_allocate (bitmap head)
103 : {
104 13759462079 : bitmap_element *element;
105 13759462079 : bitmap_obstack *bit_obstack = head->obstack;
106 :
107 13759462079 : if (bit_obstack)
108 : {
109 13620544630 : element = bit_obstack->elements;
110 :
111 13620544630 : if (element)
112 : /* Use up the inner list first before looking at the next
113 : element of the outer list. */
114 10293923708 : if (element->next)
115 : {
116 2970352479 : bit_obstack->elements = element->next;
117 2970352479 : bit_obstack->elements->prev = element->prev;
118 : }
119 : else
120 : /* Inner list was just a singleton. */
121 7323571229 : bit_obstack->elements = element->prev;
122 : else
123 3326620922 : element = XOBNEW (&bit_obstack->obstack, bitmap_element);
124 : }
125 : else
126 : {
127 138917449 : element = bitmap_ggc_free;
128 138917449 : if (element)
129 : /* Use up the inner list first before looking at the next
130 : element of the outer list. */
131 113461386 : if (element->next)
132 : {
133 14032625 : bitmap_ggc_free = element->next;
134 14032625 : bitmap_ggc_free->prev = element->prev;
135 : }
136 : else
137 : /* Inner list was just a singleton. */
138 99428761 : bitmap_ggc_free = element->prev;
139 : else
140 25456063 : element = ggc_alloc<bitmap_element> ();
141 : }
142 :
143 13759462079 : if (GATHER_STATISTICS)
144 : register_overhead (head, sizeof (bitmap_element));
145 :
146 13759462079 : memset (element->bits, 0, sizeof (element->bits));
147 :
148 13759462079 : 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 7289224382 : bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
156 : {
157 7289224382 : bitmap_element *prev;
158 7289224382 : bitmap_obstack *bit_obstack = head->obstack;
159 :
160 7289224382 : if (!elt)
161 : return;
162 :
163 6899787383 : if (head->tree_form)
164 53745354 : elt = bitmap_tree_listify_from (head, elt);
165 :
166 6899787383 : 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 6899787383 : prev = elt->prev;
175 6899787383 : if (prev)
176 : {
177 121618980 : prev->next = NULL;
178 121618980 : if (head->current->indx > prev->indx)
179 : {
180 481187 : head->current = prev;
181 481187 : head->indx = prev->indx;
182 : }
183 : }
184 : else
185 : {
186 6778168403 : head->first = NULL;
187 6778168403 : head->current = NULL;
188 6778168403 : head->indx = 0;
189 : }
190 :
191 : /* Put the entire list onto the freelist in one operation. */
192 6899787383 : if (bit_obstack)
193 : {
194 6798485502 : elt->prev = bit_obstack->elements;
195 6798485502 : bit_obstack->elements = elt;
196 : }
197 : else
198 : {
199 101301881 : elt->prev = bitmap_ggc_free;
200 101301881 : 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 7407930709 : bitmap_list_link_element (bitmap head, bitmap_element *element)
213 : {
214 7407930709 : unsigned int indx = element->indx;
215 7407930709 : bitmap_element *ptr;
216 :
217 7407930709 : gcc_checking_assert (!head->tree_form);
218 :
219 : /* If this is the first and only element, set it in. */
220 7407930709 : if (head->first == 0)
221 : {
222 5906514330 : element->next = element->prev = 0;
223 5906514330 : 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 1501416379 : else if (indx < head->indx)
229 : {
230 516338922 : for (ptr = head->current;
231 516338922 : ptr->prev != 0 && ptr->prev->indx > indx;
232 : ptr = ptr->prev)
233 : ;
234 :
235 516338922 : if (ptr->prev)
236 128824975 : ptr->prev->next = element;
237 : else
238 387513947 : head->first = element;
239 :
240 516338922 : element->prev = ptr->prev;
241 516338922 : element->next = ptr;
242 516338922 : ptr->prev = element;
243 : }
244 :
245 : /* Otherwise, it must go someplace after the current element. */
246 : else
247 : {
248 985077457 : for (ptr = head->current;
249 985077457 : ptr->next != 0 && ptr->next->indx < indx;
250 : ptr = ptr->next)
251 : ;
252 :
253 985077457 : if (ptr->next)
254 57105384 : ptr->next->prev = element;
255 :
256 985077457 : element->next = ptr->next;
257 985077457 : element->prev = ptr;
258 985077457 : ptr->next = element;
259 : }
260 :
261 : /* Set up so this is the first element searched. */
262 7407930709 : head->current = element;
263 7407930709 : head->indx = indx;
264 7407930709 : }
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 736880408 : bitmap_list_unlink_element (bitmap head, bitmap_element *element,
271 : bool to_freelist = true)
272 : {
273 736880408 : bitmap_element *next = element->next;
274 736880408 : bitmap_element *prev = element->prev;
275 :
276 736880408 : gcc_checking_assert (!head->tree_form);
277 :
278 736880408 : if (prev)
279 347639016 : prev->next = next;
280 :
281 736880408 : if (next)
282 262413560 : next->prev = prev;
283 :
284 736880408 : if (head->first == element)
285 389241392 : 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 736880408 : if (head->current == element)
290 : {
291 618395816 : head->current = next != 0 ? next : prev;
292 618395816 : if (head->current)
293 342741339 : head->indx = head->current->indx;
294 : else
295 275654477 : head->indx = 0;
296 : }
297 :
298 736880408 : if (to_freelist)
299 732317390 : bitmap_elem_to_freelist (head, element);
300 736880408 : }
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 3774605092 : bitmap_list_insert_element_after (bitmap head,
308 : bitmap_element *elt, unsigned int indx,
309 : bitmap_element *node = NULL)
310 : {
311 3774605092 : if (!node)
312 3770042074 : node = bitmap_element_allocate (head);
313 3774605092 : node->indx = indx;
314 :
315 3774605092 : gcc_checking_assert (!head->tree_form);
316 :
317 3774605092 : if (!elt)
318 : {
319 1769015746 : if (!head->current)
320 : {
321 1716341718 : head->current = node;
322 1716341718 : head->indx = indx;
323 : }
324 1769015746 : node->next = head->first;
325 1769015746 : if (node->next)
326 52674028 : node->next->prev = node;
327 1769015746 : head->first = node;
328 1769015746 : node->prev = NULL;
329 : }
330 : else
331 : {
332 2005589346 : gcc_checking_assert (head->current);
333 2005589346 : node->next = elt->next;
334 2005589346 : if (node->next)
335 77256134 : node->next->prev = node;
336 2005589346 : elt->next = node;
337 2005589346 : node->prev = elt;
338 : }
339 3774605092 : 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 95709893903 : bitmap_list_find_element (bitmap head, unsigned int indx)
349 : {
350 95709893903 : bitmap_element *element;
351 :
352 95709893903 : if (head->current == NULL
353 79965554037 : || head->indx == indx)
354 : return head->current;
355 :
356 11331041147 : if (head->current == head->first
357 5698122630 : && 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 7826647953 : bitmap_usage *usage = NULL;
363 7826647953 : 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 7826647953 : if (GATHER_STATISTICS && usage)
369 : usage->m_nsearches++;
370 :
371 7826647953 : if (head->indx < indx)
372 : /* INDX is beyond head->indx. Search from head->current
373 : forward. */
374 : for (element = head->current;
375 9430471579 : element->next != 0 && element->indx < indx;
376 : element = element->next)
377 : {
378 : if (GATHER_STATISTICS && usage)
379 : usage->m_search_iter++;
380 : }
381 :
382 4135189479 : 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 2764489999 : 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 4697529728 : 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 7826647953 : gcc_checking_assert (element != NULL);
407 7826647953 : head->current = element;
408 7826647953 : head->indx = element->indx;
409 7826647953 : if (element->indx != indx)
410 6789492276 : 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 243389088 : bitmap_tree_link_left (bitmap_element * &t, bitmap_element * &l)
429 : {
430 243389088 : l->next = t;
431 243389088 : l = t;
432 243389088 : t = t->next;
433 243389088 : }
434 :
435 : static inline void
436 267020514 : bitmap_tree_link_right (bitmap_element * &t, bitmap_element * &r)
437 : {
438 267020514 : r->prev = t;
439 267020514 : r = t;
440 267020514 : t = t->prev;
441 267020514 : }
442 :
443 : static inline void
444 85693353 : bitmap_tree_rotate_left (bitmap_element * &t)
445 : {
446 85693353 : bitmap_element *e = t->next;
447 85693353 : t->next = t->next->prev;
448 85693353 : e->prev = t;
449 85693353 : t = e;
450 85693353 : }
451 :
452 : static inline void
453 91129762 : bitmap_tree_rotate_right (bitmap_element * &t)
454 : {
455 91129762 : bitmap_element *e = t->prev;
456 91129762 : t->prev = t->prev->next;
457 91129762 : e->next = t;
458 91129762 : t = e;
459 91129762 : }
460 :
461 : static bitmap_element *
462 784254175 : bitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx)
463 : {
464 784254175 : bitmap_element N, *l, *r;
465 :
466 784254175 : if (t == NULL)
467 : return NULL;
468 :
469 784254175 : bitmap_usage *usage = NULL;
470 784254175 : if (GATHER_STATISTICS)
471 : usage = bitmap_mem_desc.get_descriptor_for_instance (head);
472 :
473 784254175 : N.prev = N.next = NULL;
474 784254175 : l = r = &N;
475 :
476 1294663777 : while (indx != t->indx)
477 : {
478 673472212 : if (GATHER_STATISTICS && usage)
479 : usage->m_search_iter++;
480 :
481 673472212 : if (indx < t->indx)
482 : {
483 347618430 : if (t->prev != NULL && indx < t->prev->indx)
484 90856385 : bitmap_tree_rotate_right (t);
485 347618430 : if (t->prev == NULL)
486 : break;
487 267020514 : bitmap_tree_link_right (t, r);
488 : }
489 325853782 : else if (indx > t->indx)
490 : {
491 325853782 : if (t->next != NULL && indx > t->next->indx)
492 85693353 : bitmap_tree_rotate_left (t);
493 325853782 : if (t->next == NULL)
494 : break;
495 243389088 : bitmap_tree_link_left (t, l);
496 : }
497 : }
498 :
499 784254175 : l->next = t->prev;
500 784254175 : r->prev = t->next;
501 784254175 : t->prev = N.next;
502 784254175 : t->next = N.prev;
503 784254175 : return t;
504 : }
505 :
506 : /* Link bitmap element E into the current bitmap splay tree. */
507 :
508 : static inline void
509 203709002 : bitmap_tree_link_element (bitmap head, bitmap_element *e)
510 : {
511 203709002 : if (head->first == NULL)
512 147435722 : e->prev = e->next = NULL;
513 : else
514 : {
515 56273280 : bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
516 56273280 : if (e->indx < t->indx)
517 : {
518 25124227 : e->prev = t->prev;
519 25124227 : e->next = t;
520 25124227 : t->prev = NULL;
521 : }
522 31149053 : else if (e->indx > t->indx)
523 : {
524 31149053 : e->next = t->next;
525 31149053 : e->prev = t;
526 31149053 : t->next = NULL;
527 : }
528 : else
529 0 : gcc_unreachable ();
530 : }
531 203709002 : head->first = e;
532 203709002 : head->current = e;
533 203709002 : head->indx = e->indx;
534 203709002 : }
535 :
536 : /* Unlink bitmap element E from the current bitmap splay tree,
537 : and return it to the freelist. */
538 :
539 : static void
540 105782322 : bitmap_tree_unlink_element (bitmap head, bitmap_element *e)
541 : {
542 105782322 : bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
543 :
544 105782322 : gcc_checking_assert (t == e);
545 :
546 105782322 : if (e->prev == NULL)
547 105034580 : t = e->next;
548 : else
549 : {
550 747742 : t = bitmap_tree_splay (head, e->prev, e->indx);
551 747742 : t->next = e->next;
552 : }
553 105782322 : head->first = t;
554 105782322 : head->current = t;
555 105782322 : head->indx = (t != NULL) ? t->indx : 0;
556 :
557 105782322 : bitmap_elem_to_freelist (head, e);
558 105782322 : }
559 :
560 : /* Return the element for INDX, or NULL if the element doesn't exist. */
561 :
562 : static inline bitmap_element *
563 3371081087 : bitmap_tree_find_element (bitmap head, unsigned int indx)
564 : {
565 3371081087 : if (head->current == NULL
566 2425857358 : || 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 505730666 : bitmap_usage *usage = NULL;
572 505730666 : 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 505730666 : if (GATHER_STATISTICS && usage)
578 : usage->m_nsearches++;
579 :
580 505730666 : bitmap_element *element = bitmap_tree_splay (head, head->first, indx);
581 505730666 : gcc_checking_assert (element != NULL);
582 505730666 : head->first = element;
583 505730666 : head->current = element;
584 505730666 : head->indx = element->indx;
585 505730666 : if (element->indx != indx)
586 106041588 : 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 61974811 : bitmap_tree_listify_from (bitmap head, bitmap_element *e)
598 : {
599 61974811 : 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 61974811 : erb = e->next;
604 61974811 : e->next = NULL;
605 61974811 : t = bitmap_tree_splay (head, head->first, e->indx);
606 61974811 : 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 61974811 : t = e->prev;
611 61974811 : head->first = t;
612 61974811 : head->current = t;
613 61974811 : head->indx = (t != NULL) ? t->indx : 0;
614 :
615 : /* Detach the tree from E, and re-attach the right branch of E. */
616 61974811 : e->prev = NULL;
617 61974811 : 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 61974811 : auto_vec<bitmap_element *, 32> stack;
627 61974811 : auto_vec<bitmap_element *, 32> sorted_elements;
628 61974811 : bitmap_element *n = e;
629 :
630 101854560 : while (true)
631 : {
632 265683931 : while (n != NULL)
633 : {
634 101854560 : stack.safe_push (n);
635 101854560 : n = n->prev;
636 : }
637 :
638 163829371 : if (stack.is_empty ())
639 : break;
640 :
641 101854560 : n = stack.pop ();
642 101854560 : sorted_elements.safe_push (n);
643 101854560 : n = n->next;
644 : }
645 :
646 61974811 : gcc_assert (sorted_elements[0] == e);
647 :
648 : bitmap_element *prev = NULL;
649 : unsigned ix;
650 163829371 : FOR_EACH_VEC_ELT (sorted_elements, ix, n)
651 : {
652 101854560 : if (prev != NULL)
653 39879749 : prev->next = n;
654 101854560 : n->prev = prev;
655 101854560 : n->next = NULL;
656 101854560 : prev = n;
657 : }
658 :
659 61974811 : return e;
660 61974811 : }
661 :
662 : /* Convert bitmap HEAD from splay-tree view to linked-list view. */
663 :
664 : void
665 10494088 : bitmap_list_view (bitmap head)
666 : {
667 10494088 : bitmap_element *ptr;
668 :
669 10494088 : gcc_assert (head->tree_form);
670 :
671 10494088 : ptr = head->first;
672 10494088 : if (ptr)
673 : {
674 8502834 : while (ptr->prev)
675 273377 : bitmap_tree_rotate_right (ptr);
676 8229457 : head->first = ptr;
677 8229457 : head->first = bitmap_tree_listify_from (head, ptr);
678 : }
679 :
680 10494088 : head->tree_form = false;
681 10494088 : if (!head->current)
682 : {
683 10494088 : head->current = head->first;
684 10494088 : head->indx = head->current ? head->current->indx : 0;
685 : }
686 10494088 : }
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 236827784 : bitmap_tree_view (bitmap head)
695 : {
696 236827784 : bitmap_element *ptr;
697 :
698 236827784 : gcc_assert (! head->tree_form);
699 :
700 236827784 : ptr = head->first;
701 245064291 : while (ptr)
702 : {
703 8236507 : ptr->prev = NULL;
704 8236507 : ptr = ptr->next;
705 : }
706 :
707 236827784 : head->tree_form = true;
708 236827784 : }
709 :
710 : /* Clear a bitmap by freeing all its elements. */
711 :
712 : void
713 13469768575 : bitmap_clear (bitmap head)
714 : {
715 13469768575 : if (head->first == NULL)
716 : return;
717 6513607579 : if (head->tree_form)
718 : {
719 : bitmap_element *e, *t;
720 70907472 : for (e = head->first; e->prev; e = e->prev)
721 : /* Loop to find the element with the smallest index. */ ;
722 53745354 : t = bitmap_tree_splay (head, head->first, e->indx);
723 53745354 : gcc_checking_assert (t == e);
724 53745354 : head->first = t;
725 : }
726 6513607579 : 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 341940681 : bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
734 : {
735 341940681 : if (!bit_obstack)
736 : {
737 45986305 : 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 330647020 : bit_obstack->elements = NULL;
747 330647020 : bit_obstack->heads = NULL;
748 330647020 : 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 341901935 : bitmap_obstack_release (bitmap_obstack *bit_obstack)
759 : {
760 341901935 : if (!bit_obstack)
761 : {
762 45965093 : if (--bitmap_default_obstack_depth)
763 : {
764 11293176 : gcc_assert (bitmap_default_obstack_depth > 0);
765 : return;
766 : }
767 : bit_obstack = &bitmap_default_obstack;
768 : }
769 :
770 330608759 : bit_obstack->elements = NULL;
771 330608759 : bit_obstack->heads = NULL;
772 330608759 : 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 3823485920 : bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL)
780 : {
781 3823485920 : bitmap map;
782 :
783 3823485920 : if (!bit_obstack)
784 : {
785 688106173 : gcc_assert (bitmap_default_obstack_depth > 0);
786 : bit_obstack = &bitmap_default_obstack;
787 : }
788 3823485920 : map = bit_obstack->heads;
789 3823485920 : if (map)
790 1256506462 : bit_obstack->heads = (class bitmap_head *) map->first;
791 : else
792 2566979458 : map = XOBNEW (&bit_obstack->obstack, bitmap_head);
793 3823485920 : bitmap_initialize (map, bit_obstack PASS_MEM_STAT);
794 :
795 3823485920 : if (GATHER_STATISTICS)
796 : register_overhead (map, sizeof (bitmap_head));
797 :
798 3823485920 : return map;
799 : }
800 :
801 : /* Create a new GCd bitmap. */
802 :
803 : bitmap
804 46503665 : bitmap_gc_alloc (ALONE_MEM_STAT_DECL)
805 : {
806 46503665 : bitmap map;
807 :
808 46503665 : map = ggc_alloc<bitmap_head> ();
809 46503665 : bitmap_initialize (map, NULL PASS_MEM_STAT);
810 :
811 46503665 : if (GATHER_STATISTICS)
812 : register_overhead (map, sizeof (bitmap_head));
813 :
814 46503665 : return map;
815 : }
816 :
817 : /* Release an obstack allocated bitmap. */
818 :
819 : void
820 2521757388 : bitmap_obstack_free (bitmap map)
821 : {
822 2521757388 : if (map)
823 : {
824 1422440645 : bitmap_clear (map);
825 1422440645 : map->first = (bitmap_element *) map->obstack->heads;
826 :
827 1422440645 : if (GATHER_STATISTICS)
828 : release_overhead (map, sizeof (bitmap_head), true);
829 :
830 1422440645 : map->obstack->heads = map;
831 : }
832 2521757388 : }
833 :
834 :
835 : /* Return nonzero if all bits in an element are zero. */
836 :
837 : static inline int
838 799529761 : bitmap_element_zerop (const bitmap_element *element)
839 : {
840 : #if BITMAP_ELEMENT_WORDS == 2
841 799529761 : 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 1988592726 : bitmap_copy (bitmap to, const_bitmap from)
857 : {
858 1988592726 : const bitmap_element *from_ptr;
859 1988592726 : bitmap_element *to_ptr = 0;
860 :
861 1988592726 : gcc_checking_assert (!to->tree_form && !from->tree_form);
862 :
863 1988592726 : bitmap_clear (to);
864 :
865 : /* Copy elements in forward direction one at a time. */
866 4366373020 : for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
867 : {
868 2377780294 : bitmap_element *to_elt = bitmap_element_allocate (to);
869 :
870 2377780294 : to_elt->indx = from_ptr->indx;
871 2377780294 : 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 2377780294 : if (to_ptr == 0)
877 : {
878 1574659562 : to->first = to->current = to_elt;
879 1574659562 : to->indx = from_ptr->indx;
880 1574659562 : to_elt->next = to_elt->prev = 0;
881 : }
882 : else
883 : {
884 803120732 : to_elt->prev = to_ptr;
885 803120732 : to_elt->next = 0;
886 803120732 : to_ptr->next = to_elt;
887 : }
888 :
889 2377780294 : to_ptr = to_elt;
890 : }
891 1988592726 : }
892 :
893 : /* Move a bitmap to another bitmap. */
894 :
895 : void
896 30930937 : bitmap_move (bitmap to, bitmap from)
897 : {
898 30930937 : gcc_assert (to->obstack == from->obstack);
899 :
900 30930937 : bitmap_clear (to);
901 :
902 30930937 : size_t sz = 0;
903 30930937 : 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 30930937 : *to = *from;
911 :
912 30930937 : if (GATHER_STATISTICS)
913 : release_overhead (from, sz, false);
914 30930937 : }
915 :
916 : /* Clear a single bit in a bitmap. Return true if the bit changed. */
917 :
918 : bool
919 25338072783 : bitmap_clear_bit (bitmap head, int bit)
920 : {
921 25338072783 : unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
922 25338072783 : bitmap_element *ptr;
923 :
924 25338072783 : if (!head->tree_form)
925 24504579257 : ptr = bitmap_list_find_element (head, indx);
926 : else
927 833493526 : ptr = bitmap_tree_find_element (head, indx);
928 25338072783 : if (ptr != 0)
929 : {
930 20530819834 : unsigned bit_num = bit % BITMAP_WORD_BITS;
931 20530819834 : unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
932 20530819834 : BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
933 20530819834 : bool res = (ptr->bits[word_num] & bit_val) != 0;
934 20530819834 : if (res)
935 : {
936 3534753445 : ptr->bits[word_num] &= ~bit_val;
937 : /* If we cleared the entire word, free up the element. */
938 3534753445 : if (!ptr->bits[word_num]
939 3534753445 : && bitmap_element_zerop (ptr))
940 : {
941 587982216 : if (!head->tree_form)
942 505226669 : bitmap_list_unlink_element (head, ptr);
943 : else
944 82755547 : bitmap_tree_unlink_element (head, ptr);
945 : }
946 : }
947 :
948 20530819834 : 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 36585443847 : bitmap_set_bit (bitmap head, int bit)
958 : {
959 36585443847 : unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
960 36585443847 : bitmap_element *ptr;
961 36585443847 : if (!head->tree_form)
962 34678944323 : ptr = bitmap_list_find_element (head, indx);
963 : else
964 1906499524 : ptr = bitmap_tree_find_element (head, indx);
965 36585443847 : unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
966 36585443847 : unsigned bit_num = bit % BITMAP_WORD_BITS;
967 36585443847 : BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
968 :
969 36585443847 : if (ptr != 0)
970 : {
971 29114560892 : bool res = (ptr->bits[word_num] & bit_val) == 0;
972 : /* Write back unconditionally to avoid branch mispredicts. */
973 29114560892 : ptr->bits[word_num] |= bit_val;
974 29114560892 : return res;
975 : }
976 :
977 7470882955 : ptr = bitmap_element_allocate (head);
978 7470882955 : ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
979 7470882955 : ptr->bits[word_num] = bit_val;
980 7470882955 : if (!head->tree_form)
981 7267306844 : bitmap_list_link_element (head, ptr);
982 : else
983 203576111 : 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 33954394562 : bitmap_bit_p (const_bitmap head, int bit)
991 : {
992 33954394562 : unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
993 33954394562 : const bitmap_element *ptr;
994 33954394562 : unsigned bit_num;
995 33954394562 : unsigned word_num;
996 :
997 33954394562 : if (!head->tree_form)
998 33337978559 : ptr = bitmap_list_find_element (const_cast<bitmap> (head), indx);
999 : else
1000 616416003 : ptr = bitmap_tree_find_element (const_cast<bitmap> (head), indx);
1001 33954394562 : if (ptr == 0)
1002 : return 0;
1003 :
1004 24480159999 : bit_num = bit % BITMAP_WORD_BITS;
1005 24480159999 : word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
1006 :
1007 24480159999 : 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 443586 : 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 443586 : gcc_checking_assert (pow2p_hwi (chunk_size));
1020 443586 : gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
1021 :
1022 : // Ensure chunk_value is within range of chunk_size bits.
1023 443586 : BITMAP_WORD max_value = (1 << chunk_size) - 1;
1024 443586 : gcc_checking_assert (chunk_value <= max_value);
1025 :
1026 443586 : unsigned bit = chunk * chunk_size;
1027 443586 : unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
1028 443586 : bitmap_element *ptr;
1029 443586 : if (!head->tree_form)
1030 64 : ptr = bitmap_list_find_element (head, indx);
1031 : else
1032 443522 : ptr = bitmap_tree_find_element (head, indx);
1033 443586 : unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
1034 443586 : unsigned bit_num = bit % BITMAP_WORD_BITS;
1035 443586 : BITMAP_WORD bit_val = chunk_value << bit_num;
1036 443586 : BITMAP_WORD mask = ~(max_value << bit_num);
1037 :
1038 443586 : if (ptr != 0)
1039 : {
1040 310683 : ptr->bits[word_num] &= mask;
1041 310683 : ptr->bits[word_num] |= bit_val;
1042 310683 : return;
1043 : }
1044 :
1045 132903 : ptr = bitmap_element_allocate (head);
1046 132903 : ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
1047 132903 : ptr->bits[word_num] = bit_val;
1048 132903 : if (!head->tree_form)
1049 12 : bitmap_list_link_element (head, ptr);
1050 : else
1051 132891 : 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 14228768 : 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 14228768 : gcc_checking_assert (pow2p_hwi (chunk_size));
1064 14228768 : gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
1065 :
1066 14228768 : BITMAP_WORD max_value = (1 << chunk_size) - 1;
1067 14228768 : unsigned bit = chunk * chunk_size;
1068 14228768 : unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
1069 14228768 : const bitmap_element *ptr;
1070 14228768 : unsigned bit_num;
1071 14228768 : unsigned word_num;
1072 :
1073 14228768 : if (!head->tree_form)
1074 256 : ptr = bitmap_list_find_element (const_cast<bitmap> (head), indx);
1075 : else
1076 14228512 : ptr = bitmap_tree_find_element (const_cast<bitmap> (head), indx);
1077 14228768 : if (ptr == 0)
1078 : return 0;
1079 :
1080 5312675 : bit_num = bit % BITMAP_WORD_BITS;
1081 5312675 : word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
1082 :
1083 : // Return 4 bits.
1084 5312675 : 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 66150425 : bitmap_count_bits_in_word (const BITMAP_WORD *bits)
1117 : {
1118 66150425 : unsigned long count = 0;
1119 :
1120 201302964 : 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 134201976 : count += __builtin_popcountl (bits[ix]);
1126 : #else
1127 : count += bitmap_popcount (bits[ix]);
1128 : #endif
1129 : }
1130 67100988 : return count;
1131 : }
1132 :
1133 : /* Count the number of bits set in the bitmap, and return it. */
1134 :
1135 : unsigned long
1136 125286442 : bitmap_count_bits (const_bitmap a)
1137 : {
1138 125286442 : unsigned long count = 0;
1139 125286442 : const bitmap_element *elt;
1140 :
1141 125286442 : gcc_checking_assert (!a->tree_form);
1142 191285125 : for (elt = a->first; elt; elt = elt->next)
1143 131997366 : count += bitmap_count_bits_in_word (elt->bits);
1144 :
1145 125286442 : return count;
1146 : }
1147 :
1148 : /* Count the number of unique bits set in A and B and return it. */
1149 :
1150 : unsigned long
1151 786984 : bitmap_count_unique_bits (const_bitmap a, const_bitmap b)
1152 : {
1153 786984 : unsigned long count = 0;
1154 786984 : const bitmap_element *elt_a, *elt_b;
1155 :
1156 1889289 : 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 1102305 : if (elt_a->indx < elt_b->indx)
1162 : {
1163 61573 : count += bitmap_count_bits_in_word (elt_a->bits);
1164 61573 : elt_a = elt_a->next;
1165 : }
1166 1040732 : else if (elt_b->indx < elt_a->indx)
1167 : {
1168 90169 : count += bitmap_count_bits_in_word (elt_b->bits);
1169 90169 : elt_b = elt_b->next;
1170 : }
1171 : else
1172 : {
1173 : BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
1174 2851689 : for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1175 1901126 : bits[ix] = elt_a->bits[ix] | elt_b->bits[ix];
1176 950563 : count += bitmap_count_bits_in_word (bits);
1177 950563 : elt_a = elt_a->next;
1178 950563 : elt_b = elt_b->next;
1179 : }
1180 : }
1181 786984 : return count;
1182 : }
1183 :
1184 : /* Return true if the bitmap has a single bit set. Otherwise return
1185 : false. */
1186 :
1187 : bool
1188 2666805 : bitmap_single_bit_set_p (const_bitmap a)
1189 : {
1190 2666805 : unsigned long count = 0;
1191 2666805 : const bitmap_element *elt;
1192 2666805 : unsigned ix;
1193 :
1194 2666805 : if (bitmap_empty_p (a))
1195 : return false;
1196 :
1197 2665427 : 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 2665427 : if (elt->next != NULL
1202 278631 : && (!a->tree_form || elt->prev != NULL))
1203 : return false;
1204 :
1205 5429578 : 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 4048364 : count += __builtin_popcountl (elt->bits[ix]);
1211 : #else
1212 : count += bitmap_popcount (elt->bits[ix]);
1213 : #endif
1214 4048364 : if (count > 1)
1215 : return false;
1216 : }
1217 :
1218 1381214 : 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 719441053 : bitmap_first_set_bit_worker (bitmap a, bool clear)
1227 : {
1228 719441053 : bitmap_element *elt = a->first;
1229 719441053 : unsigned bit_no;
1230 719441053 : BITMAP_WORD word;
1231 719441053 : unsigned ix;
1232 :
1233 719441053 : gcc_checking_assert (elt);
1234 :
1235 719441053 : if (a->tree_form)
1236 310777104 : while (elt->prev)
1237 : elt = elt->prev;
1238 :
1239 719441053 : bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
1240 907992396 : for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1241 : {
1242 907992396 : word = elt->bits[ix];
1243 907992396 : if (word)
1244 719441053 : goto found_bit;
1245 : }
1246 0 : gcc_unreachable ();
1247 719441053 : found_bit:
1248 719441053 : bit_no += ix * BITMAP_WORD_BITS;
1249 :
1250 : #if GCC_VERSION >= 3004
1251 719441053 : gcc_assert (sizeof (long) == sizeof (word));
1252 719441053 : 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 719441053 : if (clear)
1277 : {
1278 224717353 : elt->bits[ix] &= ~((BITMAP_WORD) 1 << (bit_no % BITMAP_WORD_BITS));
1279 : /* If we cleared the entire word, free up the element. */
1280 224717353 : if (!elt->bits[ix]
1281 224717353 : && bitmap_element_zerop (elt))
1282 : {
1283 46334088 : if (!a->tree_form)
1284 23307313 : bitmap_list_unlink_element (a, elt);
1285 : else
1286 23026775 : bitmap_tree_unlink_element (a, elt);
1287 : }
1288 : }
1289 :
1290 719441053 : 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 494723700 : bitmap_first_set_bit (const_bitmap a)
1298 : {
1299 494723700 : 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 224717353 : bitmap_clear_first_set_bit (bitmap a)
1307 : {
1308 224717353 : 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 >= 0; ix--)
1333 : {
1334 0 : word = elt->bits[ix];
1335 0 : if (word)
1336 0 : goto found_bit;
1337 : }
1338 0 : gcc_unreachable ();
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 717591117 : bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
1366 : {
1367 717591117 : bitmap_element *dst_elt = dst->first;
1368 717591117 : const bitmap_element *a_elt = a->first;
1369 717591117 : const bitmap_element *b_elt = b->first;
1370 717591117 : bitmap_element *dst_prev = NULL;
1371 :
1372 717591117 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
1373 717591117 : gcc_assert (dst != a && dst != b);
1374 :
1375 717591117 : if (a == b)
1376 : {
1377 0 : bitmap_copy (dst, a);
1378 0 : return;
1379 : }
1380 :
1381 1691926210 : while (a_elt && b_elt)
1382 : {
1383 974335093 : if (a_elt->indx < b_elt->indx)
1384 25589519 : a_elt = a_elt->next;
1385 948745574 : else if (b_elt->indx < a_elt->indx)
1386 181197118 : b_elt = b_elt->next;
1387 : else
1388 : {
1389 : /* Matching elts, generate A & B. */
1390 767548456 : unsigned ix;
1391 767548456 : BITMAP_WORD ior = 0;
1392 :
1393 767548456 : if (!dst_elt)
1394 247977721 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
1395 : a_elt->indx);
1396 : else
1397 519570735 : dst_elt->indx = a_elt->indx;
1398 2302645368 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1399 : {
1400 1535096912 : BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
1401 :
1402 1535096912 : dst_elt->bits[ix] = r;
1403 1535096912 : ior |= r;
1404 : }
1405 767548456 : if (ior)
1406 : {
1407 459953967 : dst_prev = dst_elt;
1408 459953967 : dst_elt = dst_elt->next;
1409 : }
1410 767548456 : a_elt = a_elt->next;
1411 767548456 : b_elt = b_elt->next;
1412 : }
1413 : }
1414 : /* Ensure that dst->current is valid. */
1415 717591117 : dst->current = dst->first;
1416 717591117 : bitmap_elt_clear_from (dst, dst_elt);
1417 717591117 : gcc_checking_assert (!dst->current == !dst->first);
1418 717591117 : if (dst->current)
1419 395788503 : dst->indx = dst->current->indx;
1420 : }
1421 :
1422 : /* A &= B. Return true if A changed. */
1423 :
1424 : bool
1425 1030117438 : bitmap_and_into (bitmap a, const_bitmap b)
1426 : {
1427 1030117438 : bitmap_element *a_elt = a->first;
1428 1030117438 : const bitmap_element *b_elt = b->first;
1429 1030117438 : bitmap_element *next;
1430 1030117438 : bool changed = false;
1431 :
1432 1030117438 : gcc_checking_assert (!a->tree_form && !b->tree_form);
1433 :
1434 1030117438 : if (a == b)
1435 : return false;
1436 :
1437 3015530777 : while (a_elt && b_elt)
1438 : {
1439 1985413339 : if (a_elt->indx < b_elt->indx)
1440 : {
1441 44294308 : next = a_elt->next;
1442 44294308 : bitmap_list_unlink_element (a, a_elt);
1443 44294308 : a_elt = next;
1444 44294308 : changed = true;
1445 : }
1446 1941119031 : else if (b_elt->indx < a_elt->indx)
1447 53639464 : b_elt = b_elt->next;
1448 : else
1449 : {
1450 : /* Matching elts, generate A &= B. */
1451 : unsigned ix;
1452 : BITMAP_WORD ior = 0;
1453 :
1454 5662438701 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1455 : {
1456 3774959134 : BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
1457 3774959134 : if (a_elt->bits[ix] != r)
1458 378954993 : changed = true;
1459 3774959134 : a_elt->bits[ix] = r;
1460 3774959134 : ior |= r;
1461 : }
1462 1887479567 : next = a_elt->next;
1463 1887479567 : if (!ior)
1464 6935770 : bitmap_list_unlink_element (a, a_elt);
1465 1887479567 : a_elt = next;
1466 1887479567 : b_elt = b_elt->next;
1467 : }
1468 : }
1469 :
1470 1030117438 : if (a_elt)
1471 : {
1472 56248694 : changed = true;
1473 56248694 : bitmap_elt_clear_from (a, a_elt);
1474 : }
1475 :
1476 1030117438 : 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 3464390427 : bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
1489 : const bitmap_element *src_elt, bool changed)
1490 : {
1491 3464390427 : if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
1492 : {
1493 : unsigned ix;
1494 :
1495 284586504 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1496 189724336 : if (src_elt->bits[ix] != dst_elt->bits[ix])
1497 : {
1498 26471609 : dst_elt->bits[ix] = src_elt->bits[ix];
1499 26471609 : changed = true;
1500 : }
1501 : }
1502 : else
1503 : {
1504 3467330526 : changed = true;
1505 3302160364 : if (!dst_elt)
1506 3204358097 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
1507 3204358097 : src_elt->indx);
1508 : else
1509 165170162 : dst_elt->indx = src_elt->indx;
1510 3369528259 : memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
1511 : }
1512 3464390427 : return changed;
1513 : }
1514 :
1515 :
1516 :
1517 : /* DST = A & ~B */
1518 :
1519 : bool
1520 190770680 : bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
1521 : {
1522 190770680 : bitmap_element *dst_elt = dst->first;
1523 190770680 : const bitmap_element *a_elt = a->first;
1524 190770680 : const bitmap_element *b_elt = b->first;
1525 190770680 : bitmap_element *dst_prev = NULL;
1526 190770680 : bitmap_element **dst_prev_pnext = &dst->first;
1527 190770680 : bool changed = false;
1528 :
1529 190770680 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
1530 190770680 : gcc_assert (dst != a && dst != b);
1531 :
1532 190770680 : if (a == b)
1533 : {
1534 0 : changed = !bitmap_empty_p (dst);
1535 0 : bitmap_clear (dst);
1536 0 : return changed;
1537 : }
1538 :
1539 552706826 : while (a_elt)
1540 : {
1541 377238802 : while (b_elt && b_elt->indx < a_elt->indx)
1542 15302656 : b_elt = b_elt->next;
1543 :
1544 361936146 : if (!b_elt || b_elt->indx > a_elt->indx)
1545 : {
1546 192687330 : changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
1547 192687330 : dst_prev = *dst_prev_pnext;
1548 192687330 : dst_prev_pnext = &dst_prev->next;
1549 192687330 : dst_elt = *dst_prev_pnext;
1550 192687330 : a_elt = a_elt->next;
1551 : }
1552 :
1553 : else
1554 : {
1555 : /* Matching elts, generate A & ~B. */
1556 169248816 : unsigned ix;
1557 169248816 : BITMAP_WORD ior = 0;
1558 :
1559 169248816 : if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1560 : {
1561 132000561 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1562 : {
1563 88000374 : BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1564 :
1565 88000374 : if (dst_elt->bits[ix] != r)
1566 : {
1567 29845004 : changed = true;
1568 29845004 : dst_elt->bits[ix] = r;
1569 : }
1570 88000374 : ior |= r;
1571 : }
1572 : }
1573 : else
1574 : {
1575 108665793 : bool new_element;
1576 125248629 : if (!dst_elt || dst_elt->indx > a_elt->indx)
1577 : {
1578 124047456 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
1579 : a_elt->indx);
1580 124047456 : new_element = true;
1581 : }
1582 : else
1583 : {
1584 1201173 : dst_elt->indx = a_elt->indx;
1585 1201173 : new_element = false;
1586 : }
1587 :
1588 375745887 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1589 : {
1590 250497258 : BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1591 :
1592 250497258 : dst_elt->bits[ix] = r;
1593 250497258 : ior |= r;
1594 : }
1595 :
1596 125248629 : if (ior)
1597 : changed = true;
1598 : else
1599 : {
1600 43359399 : changed |= !new_element;
1601 43359399 : bitmap_list_unlink_element (dst, dst_elt);
1602 43359399 : dst_elt = *dst_prev_pnext;
1603 : }
1604 : }
1605 :
1606 87359586 : if (ior)
1607 : {
1608 124972748 : dst_prev = *dst_prev_pnext;
1609 124972748 : dst_prev_pnext = &dst_prev->next;
1610 124972748 : dst_elt = *dst_prev_pnext;
1611 : }
1612 169248816 : a_elt = a_elt->next;
1613 169248816 : b_elt = b_elt->next;
1614 : }
1615 : }
1616 :
1617 : /* Ensure that dst->current is valid. */
1618 190770680 : dst->current = dst->first;
1619 :
1620 190770680 : if (dst_elt)
1621 : {
1622 1765847 : changed = true;
1623 1765847 : bitmap_elt_clear_from (dst, dst_elt);
1624 : }
1625 190770680 : gcc_checking_assert (!dst->current == !dst->first);
1626 190770680 : if (dst->current)
1627 143664403 : dst->indx = dst->current->indx;
1628 :
1629 : return changed;
1630 : }
1631 :
1632 : /* A &= ~B. Returns true if A changes */
1633 :
1634 : bool
1635 417656493 : bitmap_and_compl_into (bitmap a, const_bitmap b)
1636 : {
1637 417656493 : bitmap_element *a_elt = a->first;
1638 417656493 : const bitmap_element *b_elt = b->first;
1639 417656493 : bitmap_element *next;
1640 417656493 : BITMAP_WORD changed = 0;
1641 :
1642 417656493 : gcc_checking_assert (!a->tree_form && !b->tree_form);
1643 :
1644 417656493 : 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 1236211248 : while (a_elt && b_elt)
1656 : {
1657 818554755 : if (a_elt->indx < b_elt->indx)
1658 169759787 : a_elt = a_elt->next;
1659 648794968 : else if (b_elt->indx < a_elt->indx)
1660 345140384 : b_elt = b_elt->next;
1661 : else
1662 : {
1663 : /* Matching elts, generate A &= ~B. */
1664 : unsigned ix;
1665 : BITMAP_WORD ior = 0;
1666 :
1667 910963752 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1668 : {
1669 607309168 : BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1670 607309168 : BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
1671 :
1672 607309168 : a_elt->bits[ix] = r;
1673 607309168 : changed |= cleared;
1674 607309168 : ior |= r;
1675 : }
1676 303654584 : next = a_elt->next;
1677 303654584 : if (!ior)
1678 13600044 : bitmap_list_unlink_element (a, a_elt);
1679 303654584 : a_elt = next;
1680 303654584 : b_elt = b_elt->next;
1681 : }
1682 : }
1683 417656493 : gcc_checking_assert (!a->current == !a->first
1684 : && (!a->current || a->indx == a->current->indx));
1685 417656493 : return changed != 0;
1686 : }
1687 :
1688 : /* Set COUNT bits from START in HEAD. */
1689 : void
1690 1649509341 : bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
1691 : {
1692 1649509341 : unsigned int first_index, end_bit_plus1, last_index;
1693 1649509341 : bitmap_element *elt, *elt_prev;
1694 1649509341 : unsigned int i;
1695 :
1696 1649509341 : gcc_checking_assert (!head->tree_form);
1697 :
1698 1649509341 : if (!count)
1699 : return;
1700 :
1701 1335588141 : if (count == 1)
1702 : {
1703 596222380 : bitmap_set_bit (head, start);
1704 596222380 : return;
1705 : }
1706 :
1707 739365761 : first_index = start / BITMAP_ELEMENT_ALL_BITS;
1708 739365761 : end_bit_plus1 = start + count;
1709 739365761 : last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1710 739365761 : 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 739365761 : if (!elt)
1717 : {
1718 140623853 : elt = bitmap_element_allocate (head);
1719 140623853 : elt->indx = first_index;
1720 140623853 : bitmap_list_link_element (head, elt);
1721 : }
1722 :
1723 739365761 : gcc_checking_assert (elt->indx == first_index);
1724 739365761 : elt_prev = elt->prev;
1725 1537585576 : for (i = first_index; i <= last_index; i++)
1726 : {
1727 798219815 : unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
1728 798219815 : unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1729 :
1730 798219815 : unsigned int first_word_to_mod;
1731 798219815 : BITMAP_WORD first_mask;
1732 798219815 : unsigned int last_word_to_mod;
1733 798219815 : BITMAP_WORD last_mask;
1734 798219815 : unsigned int ix;
1735 :
1736 798219815 : if (!elt || elt->indx != i)
1737 58601445 : elt = bitmap_list_insert_element_after (head, elt_prev, i);
1738 :
1739 798219815 : if (elt_start_bit <= start)
1740 : {
1741 : /* The first bit to turn on is somewhere inside this
1742 : elt. */
1743 739365761 : first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1744 :
1745 : /* This mask should have 1s in all bits >= start position. */
1746 739365761 : first_mask =
1747 739365761 : (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1748 739365761 : 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 798219815 : 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 734929549 : last_word_to_mod =
1767 734929549 : (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1768 :
1769 : /* The last mask should have 1s below the end bit. */
1770 734929549 : last_mask =
1771 734929549 : (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
1772 : }
1773 :
1774 798219815 : if (first_word_to_mod == last_word_to_mod)
1775 : {
1776 726116883 : BITMAP_WORD mask = first_mask & last_mask;
1777 726116883 : elt->bits[first_word_to_mod] |= mask;
1778 : }
1779 : else
1780 : {
1781 72102932 : elt->bits[first_word_to_mod] |= first_mask;
1782 72102932 : 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 72102932 : elt->bits[last_word_to_mod] |= last_mask;
1786 : }
1787 :
1788 798219815 : elt_prev = elt;
1789 798219815 : elt = elt->next;
1790 : }
1791 :
1792 739365761 : head->current = elt ? elt : elt_prev;
1793 739365761 : head->indx = head->current->indx;
1794 : }
1795 :
1796 : /* Clear COUNT bits from START in HEAD. */
1797 : void
1798 2859711455 : bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
1799 : {
1800 2859711455 : unsigned int first_index, end_bit_plus1, last_index;
1801 2859711455 : bitmap_element *elt;
1802 :
1803 2859711455 : gcc_checking_assert (!head->tree_form);
1804 :
1805 2859711455 : if (!count)
1806 : return;
1807 :
1808 2859711048 : if (count == 1)
1809 : {
1810 410685365 : bitmap_clear_bit (head, start);
1811 410685365 : return;
1812 : }
1813 :
1814 2449025683 : first_index = start / BITMAP_ELEMENT_ALL_BITS;
1815 2449025683 : end_bit_plus1 = start + count;
1816 2449025683 : last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1817 2449025683 : 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 2449025683 : if (!elt)
1823 : {
1824 1683054143 : if (head->current)
1825 : {
1826 1627210156 : if (head->indx < first_index)
1827 : {
1828 1153053216 : elt = head->current->next;
1829 1153053216 : if (!elt)
1830 : return;
1831 : }
1832 : else
1833 : elt = head->current;
1834 : }
1835 : else
1836 : return;
1837 : }
1838 :
1839 2726755204 : while (elt && (elt->indx <= last_index))
1840 : {
1841 927700363 : bitmap_element * next_elt = elt->next;
1842 927700363 : unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
1843 927700363 : unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1844 :
1845 :
1846 927700363 : 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 52524115 : bitmap_list_unlink_element (head, elt);
1849 : else
1850 : {
1851 : /* Going to have to knock out some bits in this elt. */
1852 875176248 : unsigned int first_word_to_mod;
1853 875176248 : BITMAP_WORD first_mask;
1854 875176248 : unsigned int last_word_to_mod;
1855 875176248 : BITMAP_WORD last_mask;
1856 875176248 : unsigned int i;
1857 875176248 : bool clear = true;
1858 :
1859 875176248 : if (elt_start_bit <= start)
1860 : {
1861 : /* The first bit to turn off is somewhere inside this
1862 : elt. */
1863 763892686 : first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1864 :
1865 : /* This mask should have 1s in all bits >= start position. */
1866 763892686 : first_mask =
1867 763892686 : (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1868 763892686 : 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 875176248 : 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 726007240 : last_word_to_mod =
1889 726007240 : (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1890 :
1891 : /* The last mask should have 1s below the end bit. */
1892 726007240 : last_mask =
1893 726007240 : (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
1894 : }
1895 :
1896 :
1897 875176248 : if (first_word_to_mod == last_word_to_mod)
1898 : {
1899 726144773 : BITMAP_WORD mask = first_mask & last_mask;
1900 726144773 : elt->bits[first_word_to_mod] &= ~mask;
1901 : }
1902 : else
1903 : {
1904 149031475 : elt->bits[first_word_to_mod] &= ~first_mask;
1905 149031475 : 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 149031475 : elt->bits[last_word_to_mod] &= ~last_mask;
1909 : }
1910 1180415386 : for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1911 1137345614 : if (elt->bits[i])
1912 : {
1913 : clear = false;
1914 : break;
1915 : }
1916 : /* Check to see if there are any bits left. */
1917 875176248 : if (clear)
1918 43069772 : bitmap_list_unlink_element (head, elt);
1919 : }
1920 : elt = next_elt;
1921 : }
1922 :
1923 1799054841 : if (elt)
1924 : {
1925 1430765215 : head->current = elt;
1926 1430765215 : 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 7363233659 : 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 7363233659 : gcc_assert (a_elt || b_elt);
2011 :
2012 7363233659 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2013 : {
2014 : /* Matching elts, generate A | B. */
2015 4200471627 : unsigned ix;
2016 :
2017 4200471627 : if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
2018 : {
2019 10984973595 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2020 : {
2021 7323315730 : BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
2022 7323315730 : if (r != dst_elt->bits[ix])
2023 : {
2024 1225663046 : dst_elt->bits[ix] = r;
2025 1225663046 : changed = true;
2026 : }
2027 : }
2028 : }
2029 : else
2030 : {
2031 941795116 : changed = true;
2032 538038709 : if (!dst_elt)
2033 135057355 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
2034 : a_elt->indx);
2035 : else
2036 403756407 : dst_elt->indx = a_elt->indx;
2037 1616441286 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2038 : {
2039 1077627524 : BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
2040 1077627524 : dst_elt->bits[ix] = r;
2041 : }
2042 : }
2043 : }
2044 : else
2045 : {
2046 : /* Copy a single element. */
2047 2926723373 : const bitmap_element *src;
2048 :
2049 3162762032 : if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
2050 : src = a_elt;
2051 : else
2052 191829072 : src = b_elt;
2053 :
2054 3118552445 : gcc_checking_assert (src);
2055 3162762032 : changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
2056 : }
2057 7363233659 : return changed;
2058 : }
2059 :
2060 :
2061 : /* DST = A | B. Return true if DST changes. */
2062 :
2063 : bool
2064 337314668 : bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
2065 : {
2066 337314668 : bitmap_element *dst_elt = dst->first;
2067 337314668 : const bitmap_element *a_elt = a->first;
2068 337314668 : const bitmap_element *b_elt = b->first;
2069 337314668 : bitmap_element *dst_prev = NULL;
2070 337314668 : bitmap_element **dst_prev_pnext = &dst->first;
2071 337314668 : bool changed = false;
2072 :
2073 337314668 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
2074 337314668 : gcc_assert (dst != a && dst != b);
2075 :
2076 942683670 : while (a_elt || b_elt)
2077 : {
2078 605369002 : changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
2079 :
2080 605369002 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2081 : {
2082 208286209 : a_elt = a_elt->next;
2083 208286209 : b_elt = b_elt->next;
2084 : }
2085 : else
2086 : {
2087 397082793 : if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
2088 33162100 : a_elt = a_elt->next;
2089 363920693 : else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
2090 363920693 : b_elt = b_elt->next;
2091 : }
2092 :
2093 605369002 : dst_prev = *dst_prev_pnext;
2094 605369002 : dst_prev_pnext = &dst_prev->next;
2095 605369002 : dst_elt = *dst_prev_pnext;
2096 : }
2097 :
2098 337314668 : if (dst_elt)
2099 : {
2100 7966 : changed = true;
2101 : /* Ensure that dst->current is valid. */
2102 7966 : dst->current = dst->first;
2103 7966 : bitmap_elt_clear_from (dst, dst_elt);
2104 : }
2105 337314668 : gcc_checking_assert (!dst->current == !dst->first);
2106 337314668 : if (dst->current)
2107 336017665 : dst->indx = dst->current->indx;
2108 337314668 : return changed;
2109 : }
2110 :
2111 : /* A |= B. Return true if A changes. */
2112 :
2113 : bool
2114 4661759561 : bitmap_ior_into (bitmap a, const_bitmap b)
2115 : {
2116 4661759561 : bitmap_element *a_elt = a->first;
2117 4661759561 : const bitmap_element *b_elt = b->first;
2118 4661759561 : bitmap_element *a_prev = NULL;
2119 4661759561 : bitmap_element **a_prev_pnext = &a->first;
2120 4661759561 : bool changed = false;
2121 :
2122 4661759561 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2123 4661759561 : if (a == b)
2124 : return false;
2125 :
2126 11185387243 : while (b_elt)
2127 : {
2128 : /* If A lags behind B, just advance it. */
2129 6523632138 : if (!a_elt || a_elt->indx == b_elt->indx)
2130 : {
2131 5640220340 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
2132 5640220340 : b_elt = b_elt->next;
2133 : }
2134 883411798 : else if (a_elt->indx > b_elt->indx)
2135 : {
2136 107654984 : changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);
2137 107654984 : b_elt = b_elt->next;
2138 : }
2139 :
2140 6523632138 : a_prev = *a_prev_pnext;
2141 6523632138 : a_prev_pnext = &a_prev->next;
2142 6523632138 : a_elt = *a_prev_pnext;
2143 : }
2144 :
2145 4661755105 : gcc_checking_assert (!a->current == !a->first);
2146 4661755105 : if (a->current)
2147 4328869434 : 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 11603669 : bitmap_ior_into_and_free (bitmap a, bitmap *b_)
2156 : {
2157 11603669 : bitmap b = *b_;
2158 11603669 : bitmap_element *a_elt = a->first;
2159 11603669 : bitmap_element *b_elt = b->first;
2160 11603669 : bitmap_element *a_prev = NULL;
2161 11603669 : bitmap_element **a_prev_pnext = &a->first;
2162 11603669 : bool changed = false;
2163 :
2164 11603669 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2165 11603669 : gcc_assert (a->obstack == b->obstack);
2166 11603669 : if (a == b)
2167 : return false;
2168 :
2169 38754120 : while (b_elt)
2170 : {
2171 : /* If A lags behind B, just advance it. */
2172 27150451 : if (!a_elt || a_elt->indx == b_elt->indx)
2173 : {
2174 16927296 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
2175 16927296 : b_elt = b_elt->next;
2176 : }
2177 10223155 : else if (a_elt->indx > b_elt->indx)
2178 : {
2179 4563018 : bitmap_element *b_elt_next = b_elt->next;
2180 4563018 : bitmap_list_unlink_element (b, b_elt, false);
2181 4563018 : bitmap_list_insert_element_after (a, a_prev, b_elt->indx, b_elt);
2182 4563018 : b_elt = b_elt_next;
2183 : }
2184 :
2185 27150451 : a_prev = *a_prev_pnext;
2186 27150451 : a_prev_pnext = &a_prev->next;
2187 27150451 : a_elt = *a_prev_pnext;
2188 : }
2189 :
2190 11603669 : gcc_checking_assert (!a->current == !a->first);
2191 11603669 : if (a->current)
2192 11603669 : a->indx = a->current->indx;
2193 :
2194 11603669 : if (b->obstack)
2195 11603669 : 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 482546523 : bitmap_equal_p (const_bitmap a, const_bitmap b)
2348 : {
2349 482546523 : const bitmap_element *a_elt;
2350 482546523 : const bitmap_element *b_elt;
2351 482546523 : unsigned ix;
2352 :
2353 482546523 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2354 :
2355 482546523 : for (a_elt = a->first, b_elt = b->first;
2356 992303755 : a_elt && b_elt;
2357 509757232 : a_elt = a_elt->next, b_elt = b_elt->next)
2358 : {
2359 623479641 : if (a_elt->indx != b_elt->indx)
2360 : return false;
2361 1615421883 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2362 1105664651 : if (a_elt->bits[ix] != b_elt->bits[ix])
2363 : return false;
2364 : }
2365 368824114 : return !a_elt && !b_elt;
2366 : }
2367 :
2368 : /* Return true if A AND B is not empty. */
2369 :
2370 : bool
2371 379059453 : bitmap_intersect_p (const_bitmap a, const_bitmap b)
2372 : {
2373 379059453 : const bitmap_element *a_elt;
2374 379059453 : const bitmap_element *b_elt;
2375 379059453 : unsigned ix;
2376 :
2377 379059453 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2378 :
2379 379059453 : for (a_elt = a->first, b_elt = b->first;
2380 753887263 : a_elt && b_elt;)
2381 : {
2382 462915635 : if (a_elt->indx < b_elt->indx)
2383 171448162 : a_elt = a_elt->next;
2384 291467473 : else if (b_elt->indx < a_elt->indx)
2385 73104921 : b_elt = b_elt->next;
2386 : else
2387 : {
2388 509617943 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2389 379343216 : if (a_elt->bits[ix] & b_elt->bits[ix])
2390 : return true;
2391 130274727 : a_elt = a_elt->next;
2392 130274727 : 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 857956831 : bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
2433 : {
2434 857956831 : bool changed = false;
2435 :
2436 857956831 : bitmap_element *dst_elt = dst->first;
2437 857956831 : const bitmap_element *a_elt = a->first;
2438 857956831 : const bitmap_element *b_elt = b->first;
2439 857956831 : const bitmap_element *kill_elt = kill->first;
2440 857956831 : bitmap_element *dst_prev = NULL;
2441 857956831 : bitmap_element **dst_prev_pnext = &dst->first;
2442 :
2443 857956831 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form
2444 : && !kill->tree_form);
2445 857956831 : gcc_assert (dst != a && dst != b && dst != kill);
2446 :
2447 : /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
2448 857956831 : if (b == kill || bitmap_empty_p (b))
2449 : {
2450 65739090 : changed = !bitmap_equal_p (dst, a);
2451 65739090 : if (changed)
2452 4035578 : bitmap_copy (dst, a);
2453 65739090 : return changed;
2454 : }
2455 792217741 : if (bitmap_empty_p (kill))
2456 287756666 : return bitmap_ior (dst, a, b);
2457 504461075 : if (bitmap_empty_p (a))
2458 36027686 : return bitmap_and_compl (dst, b, kill);
2459 :
2460 1557650525 : while (a_elt || b_elt)
2461 : {
2462 1089217136 : bool new_element = false;
2463 :
2464 1089217136 : if (b_elt)
2465 1085815792 : while (kill_elt && kill_elt->indx < b_elt->indx)
2466 26097585 : kill_elt = kill_elt->next;
2467 :
2468 1089217136 : if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
2469 599194920 : && (!a_elt || a_elt->indx >= b_elt->indx))
2470 : {
2471 593068901 : bitmap_element tmp_elt;
2472 593068901 : unsigned ix;
2473 :
2474 593068901 : BITMAP_WORD ior = 0;
2475 593068901 : tmp_elt.indx = b_elt->indx;
2476 1779206703 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2477 : {
2478 1186137802 : BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
2479 1186137802 : ior |= r;
2480 1186137802 : tmp_elt.bits[ix] = r;
2481 : }
2482 :
2483 593068901 : if (ior)
2484 : {
2485 550213777 : changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
2486 : a_elt, &tmp_elt, changed);
2487 550213777 : new_element = true;
2488 550213777 : if (a_elt && a_elt->indx == b_elt->indx)
2489 480799672 : a_elt = a_elt->next;
2490 : }
2491 :
2492 593068901 : b_elt = b_elt->next;
2493 593068901 : kill_elt = kill_elt->next;
2494 : }
2495 : else
2496 : {
2497 496148235 : changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
2498 : a_elt, b_elt, changed);
2499 496148235 : new_element = true;
2500 :
2501 496148235 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2502 : {
2503 135740422 : a_elt = a_elt->next;
2504 135740422 : b_elt = b_elt->next;
2505 : }
2506 : else
2507 : {
2508 360407813 : if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
2509 50480770 : a_elt = a_elt->next;
2510 309927043 : else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
2511 309927043 : b_elt = b_elt->next;
2512 : }
2513 : }
2514 :
2515 1089217136 : if (new_element)
2516 : {
2517 1046362012 : dst_prev = *dst_prev_pnext;
2518 1046362012 : dst_prev_pnext = &dst_prev->next;
2519 1046362012 : dst_elt = *dst_prev_pnext;
2520 : }
2521 : }
2522 :
2523 468433389 : if (dst_elt)
2524 : {
2525 3179 : changed = true;
2526 : /* Ensure that dst->current is valid. */
2527 3179 : dst->current = dst->first;
2528 3179 : bitmap_elt_clear_from (dst, dst_elt);
2529 : }
2530 468433389 : gcc_checking_assert (!dst->current == !dst->first);
2531 468433389 : if (dst->current)
2532 468433389 : dst->indx = dst->current->indx;
2533 :
2534 : return changed;
2535 : }
2536 :
2537 : /* A |= (B & ~C). Return true if A changes. */
2538 :
2539 : bool
2540 53151209 : bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c)
2541 : {
2542 53151209 : bitmap_element *a_elt = a->first;
2543 53151209 : const bitmap_element *b_elt = b->first;
2544 53151209 : const bitmap_element *c_elt = c->first;
2545 53151209 : bitmap_element and_elt;
2546 53151209 : bitmap_element *a_prev = NULL;
2547 53151209 : bitmap_element **a_prev_pnext = &a->first;
2548 53151209 : bool changed = false;
2549 53151209 : unsigned ix;
2550 :
2551 53151209 : gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
2552 :
2553 53151209 : if (a == b)
2554 : return false;
2555 52842265 : if (bitmap_empty_p (c))
2556 11437629 : return bitmap_ior_into (a, b);
2557 41404636 : else if (bitmap_empty_p (a))
2558 21208964 : return bitmap_and_compl (a, b, c);
2559 :
2560 20195672 : and_elt.indx = -1;
2561 66587066 : while (b_elt)
2562 : {
2563 : /* Advance C. */
2564 58511962 : while (c_elt && c_elt->indx < b_elt->indx)
2565 12120568 : c_elt = c_elt->next;
2566 :
2567 46391394 : const bitmap_element *and_elt_ptr;
2568 46391394 : if (c_elt && c_elt->indx == b_elt->indx)
2569 : {
2570 13347039 : BITMAP_WORD overall = 0;
2571 13347039 : and_elt_ptr = &and_elt;
2572 13347039 : and_elt.indx = b_elt->indx;
2573 40041117 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2574 : {
2575 26694078 : and_elt.bits[ix] = b_elt->bits[ix] & ~c_elt->bits[ix];
2576 26694078 : overall |= and_elt.bits[ix];
2577 : }
2578 13347039 : if (!overall)
2579 : {
2580 1254435 : b_elt = b_elt->next;
2581 1254435 : continue;
2582 : }
2583 : }
2584 : else
2585 : and_elt_ptr = b_elt;
2586 :
2587 45136959 : b_elt = b_elt->next;
2588 :
2589 : /* Now find a place to insert AND_ELT. */
2590 52318294 : do
2591 : {
2592 52318294 : ix = a_elt ? a_elt->indx : and_elt_ptr->indx;
2593 52318294 : if (ix == and_elt_ptr->indx)
2594 43902135 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt,
2595 : and_elt_ptr, changed);
2596 8416159 : else if (ix > and_elt_ptr->indx)
2597 1234824 : changed = bitmap_elt_copy (a, NULL, a_prev, and_elt_ptr, changed);
2598 :
2599 52318294 : a_prev = *a_prev_pnext;
2600 52318294 : a_prev_pnext = &a_prev->next;
2601 52318294 : a_elt = *a_prev_pnext;
2602 :
2603 : /* If A lagged behind B/C, we advanced it so loop once more. */
2604 : }
2605 52318294 : while (ix < and_elt_ptr->indx);
2606 : }
2607 :
2608 20195672 : gcc_checking_assert (!a->current == !a->first);
2609 20195672 : if (a->current)
2610 20195672 : a->indx = a->current->indx;
2611 : return changed;
2612 : }
2613 :
2614 : /* A |= (B & C). Return true if A changes. */
2615 :
2616 : bool
2617 11541218 : bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
2618 : {
2619 11541218 : bitmap_element *a_elt = a->first;
2620 11541218 : const bitmap_element *b_elt = b->first;
2621 11541218 : const bitmap_element *c_elt = c->first;
2622 11541218 : bitmap_element and_elt;
2623 11541218 : bitmap_element *a_prev = NULL;
2624 11541218 : bitmap_element **a_prev_pnext = &a->first;
2625 11541218 : bool changed = false;
2626 11541218 : unsigned ix;
2627 :
2628 11541218 : gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
2629 :
2630 11541218 : if (b == c)
2631 0 : return bitmap_ior_into (a, b);
2632 11541218 : if (bitmap_empty_p (b) || bitmap_empty_p (c))
2633 : return false;
2634 :
2635 : and_elt.indx = -1;
2636 26511376 : while (b_elt && c_elt)
2637 : {
2638 : BITMAP_WORD overall;
2639 :
2640 : /* Find a common item of B and C. */
2641 21488150 : while (b_elt->indx != c_elt->indx)
2642 : {
2643 6517990 : if (b_elt->indx < c_elt->indx)
2644 : {
2645 700327 : b_elt = b_elt->next;
2646 700327 : if (!b_elt)
2647 199951 : goto done;
2648 : }
2649 : else
2650 : {
2651 5817663 : c_elt = c_elt->next;
2652 5817663 : if (!c_elt)
2653 195705 : goto done;
2654 : }
2655 : }
2656 :
2657 14970160 : overall = 0;
2658 14970160 : and_elt.indx = b_elt->indx;
2659 44910480 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2660 : {
2661 29940320 : and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
2662 29940320 : overall |= and_elt.bits[ix];
2663 : }
2664 :
2665 14970160 : b_elt = b_elt->next;
2666 14970160 : c_elt = c_elt->next;
2667 14970160 : if (!overall)
2668 4466029 : continue;
2669 :
2670 : /* Now find a place to insert AND_ELT. */
2671 10504240 : do
2672 : {
2673 10504240 : ix = a_elt ? a_elt->indx : and_elt.indx;
2674 10504240 : if (ix == and_elt.indx)
2675 10452874 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
2676 51366 : else if (ix > and_elt.indx)
2677 51257 : changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
2678 :
2679 10504240 : a_prev = *a_prev_pnext;
2680 10504240 : a_prev_pnext = &a_prev->next;
2681 10504240 : a_elt = *a_prev_pnext;
2682 :
2683 : /* If A lagged behind B/C, we advanced it so loop once more. */
2684 : }
2685 10504240 : while (ix < and_elt.indx);
2686 : }
2687 :
2688 11145560 : done:
2689 11541216 : gcc_checking_assert (!a->current == !a->first);
2690 11541216 : if (a->current)
2691 8891780 : a->indx = a->current->indx;
2692 : return changed;
2693 : }
2694 :
2695 : /* Compute hash of bitmap (for purposes of hashing). */
2696 :
2697 : hashval_t
2698 262584602 : bitmap_hash (const_bitmap head)
2699 : {
2700 262584602 : const bitmap_element *ptr;
2701 262584602 : BITMAP_WORD hash = 0;
2702 262584602 : int ix;
2703 :
2704 262584602 : gcc_checking_assert (!head->tree_form);
2705 :
2706 599138055 : for (ptr = head->first; ptr; ptr = ptr->next)
2707 : {
2708 336553453 : hash ^= ptr->indx;
2709 1009660359 : for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
2710 673106906 : hash ^= ptr->bits[ix];
2711 : }
2712 262584602 : 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"
|
