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 834704413 : bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
79 : {
80 834704413 : bitmap_obstack *bit_obstack = head->obstack;
81 :
82 834704413 : if (GATHER_STATISTICS)
83 : release_overhead (head, sizeof (bitmap_element), false);
84 :
85 834704413 : elt->next = NULL;
86 834704413 : elt->indx = -1;
87 834704413 : if (bit_obstack)
88 : {
89 831484073 : elt->prev = bit_obstack->elements;
90 831484073 : bit_obstack->elements = elt;
91 : }
92 : else
93 : {
94 3220340 : elt->prev = bitmap_ggc_free;
95 3220340 : 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 13704939999 : bitmap_element_allocate (bitmap head)
103 : {
104 13704939999 : bitmap_element *element;
105 13704939999 : bitmap_obstack *bit_obstack = head->obstack;
106 :
107 13704939999 : if (bit_obstack)
108 : {
109 13566367116 : element = bit_obstack->elements;
110 :
111 13566367116 : if (element)
112 : /* Use up the inner list first before looking at the next
113 : element of the outer list. */
114 10257304249 : if (element->next)
115 : {
116 2966258890 : bit_obstack->elements = element->next;
117 2966258890 : bit_obstack->elements->prev = element->prev;
118 : }
119 : else
120 : /* Inner list was just a singleton. */
121 7291045359 : bit_obstack->elements = element->prev;
122 : else
123 3309062867 : element = XOBNEW (&bit_obstack->obstack, bitmap_element);
124 : }
125 : else
126 : {
127 138572883 : element = bitmap_ggc_free;
128 138572883 : if (element)
129 : /* Use up the inner list first before looking at the next
130 : element of the outer list. */
131 113089252 : if (element->next)
132 : {
133 14019692 : bitmap_ggc_free = element->next;
134 14019692 : bitmap_ggc_free->prev = element->prev;
135 : }
136 : else
137 : /* Inner list was just a singleton. */
138 99069560 : bitmap_ggc_free = element->prev;
139 : else
140 25483631 : element = ggc_alloc<bitmap_element> ();
141 : }
142 :
143 13704939999 : if (GATHER_STATISTICS)
144 : register_overhead (head, sizeof (bitmap_element));
145 :
146 13704939999 : memset (element->bits, 0, sizeof (element->bits));
147 :
148 13704939999 : 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 7258188906 : bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
156 : {
157 7258188906 : bitmap_element *prev;
158 7258188906 : bitmap_obstack *bit_obstack = head->obstack;
159 :
160 7258188906 : if (!elt)
161 : return;
162 :
163 6869040685 : if (head->tree_form)
164 53370168 : elt = bitmap_tree_listify_from (head, elt);
165 :
166 6869040685 : 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 6869040685 : prev = elt->prev;
175 6869040685 : if (prev)
176 : {
177 121306233 : prev->next = NULL;
178 121306233 : if (head->current->indx > prev->indx)
179 : {
180 481439 : head->current = prev;
181 481439 : head->indx = prev->indx;
182 : }
183 : }
184 : else
185 : {
186 6747734452 : head->first = NULL;
187 6747734452 : head->current = NULL;
188 6747734452 : head->indx = 0;
189 : }
190 :
191 : /* Put the entire list onto the freelist in one operation. */
192 6869040685 : if (bit_obstack)
193 : {
194 6768089210 : elt->prev = bit_obstack->elements;
195 6768089210 : bit_obstack->elements = elt;
196 : }
197 : else
198 : {
199 100951475 : elt->prev = bitmap_ggc_free;
200 100951475 : 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 7367760732 : bitmap_list_link_element (bitmap head, bitmap_element *element)
213 : {
214 7367760732 : unsigned int indx = element->indx;
215 7367760732 : bitmap_element *ptr;
216 :
217 7367760732 : gcc_checking_assert (!head->tree_form);
218 :
219 : /* If this is the first and only element, set it in. */
220 7367760732 : if (head->first == 0)
221 : {
222 5872647022 : element->next = element->prev = 0;
223 5872647022 : 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 1495113710 : else if (indx < head->indx)
229 : {
230 514501730 : for (ptr = head->current;
231 514501730 : ptr->prev != 0 && ptr->prev->indx > indx;
232 : ptr = ptr->prev)
233 : ;
234 :
235 514501730 : if (ptr->prev)
236 128108850 : ptr->prev->next = element;
237 : else
238 386392880 : head->first = element;
239 :
240 514501730 : element->prev = ptr->prev;
241 514501730 : element->next = ptr;
242 514501730 : ptr->prev = element;
243 : }
244 :
245 : /* Otherwise, it must go someplace after the current element. */
246 : else
247 : {
248 980611980 : for (ptr = head->current;
249 980611980 : ptr->next != 0 && ptr->next->indx < indx;
250 : ptr = ptr->next)
251 : ;
252 :
253 980611980 : if (ptr->next)
254 56792057 : ptr->next->prev = element;
255 :
256 980611980 : element->next = ptr->next;
257 980611980 : element->prev = ptr;
258 980611980 : ptr->next = element;
259 : }
260 :
261 : /* Set up so this is the first element searched. */
262 7367760732 : head->current = element;
263 7367760732 : head->indx = indx;
264 7367760732 : }
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 733932713 : bitmap_list_unlink_element (bitmap head, bitmap_element *element,
271 : bool to_freelist = true)
272 : {
273 733932713 : bitmap_element *next = element->next;
274 733932713 : bitmap_element *prev = element->prev;
275 :
276 733932713 : gcc_checking_assert (!head->tree_form);
277 :
278 733932713 : if (prev)
279 345968309 : prev->next = next;
280 :
281 733932713 : if (next)
282 261187272 : next->prev = prev;
283 :
284 733932713 : if (head->first == element)
285 387964404 : 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 733932713 : if (head->current == element)
290 : {
291 615625324 : head->current = next != 0 ? next : prev;
292 615625324 : if (head->current)
293 341173077 : head->indx = head->current->indx;
294 : else
295 274452247 : head->indx = 0;
296 : }
297 :
298 733932713 : if (to_freelist)
299 729394184 : bitmap_elem_to_freelist (head, element);
300 733932713 : }
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 3767830773 : bitmap_list_insert_element_after (bitmap head,
308 : bitmap_element *elt, unsigned int indx,
309 : bitmap_element *node = NULL)
310 : {
311 3767830773 : if (!node)
312 3763292244 : node = bitmap_element_allocate (head);
313 3767830773 : node->indx = indx;
314 :
315 3767830773 : gcc_checking_assert (!head->tree_form);
316 :
317 3767830773 : if (!elt)
318 : {
319 1763953451 : if (!head->current)
320 : {
321 1711406852 : head->current = node;
322 1711406852 : head->indx = indx;
323 : }
324 1763953451 : node->next = head->first;
325 1763953451 : if (node->next)
326 52546599 : node->next->prev = node;
327 1763953451 : head->first = node;
328 1763953451 : node->prev = NULL;
329 : }
330 : else
331 : {
332 2003877322 : gcc_checking_assert (head->current);
333 2003877322 : node->next = elt->next;
334 2003877322 : if (node->next)
335 76591561 : node->next->prev = node;
336 2003877322 : elt->next = node;
337 2003877322 : node->prev = elt;
338 : }
339 3767830773 : 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 95094972875 : bitmap_list_find_element (bitmap head, unsigned int indx)
349 : {
350 95094972875 : bitmap_element *element;
351 :
352 95094972875 : if (head->current == NULL
353 79451433038 : || head->indx == indx)
354 : return head->current;
355 :
356 11264528967 : if (head->current == head->first
357 5666906013 : && 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 7776997832 : bitmap_usage *usage = NULL;
363 7776997832 : 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 7776997832 : if (GATHER_STATISTICS && usage)
369 : usage->m_nsearches++;
370 :
371 7776997832 : if (head->indx < indx)
372 : /* INDX is beyond head->indx. Search from head->current
373 : forward. */
374 : for (element = head->current;
375 9384756046 : element->next != 0 && element->indx < indx;
376 : element = element->next)
377 : {
378 : if (GATHER_STATISTICS && usage)
379 : usage->m_search_iter++;
380 : }
381 :
382 4106018592 : 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 2739498680 : 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 4668022457 : 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 7776997832 : gcc_checking_assert (element != NULL);
407 7776997832 : head->current = element;
408 7776997832 : head->indx = element->indx;
409 7776997832 : if (element->indx != indx)
410 6752428372 : 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 242243875 : bitmap_tree_link_left (bitmap_element * &t, bitmap_element * &l)
429 : {
430 242243875 : l->next = t;
431 242243875 : l = t;
432 242243875 : t = t->next;
433 242243875 : }
434 :
435 : static inline void
436 265688851 : bitmap_tree_link_right (bitmap_element * &t, bitmap_element * &r)
437 : {
438 265688851 : r->prev = t;
439 265688851 : r = t;
440 265688851 : t = t->prev;
441 265688851 : }
442 :
443 : static inline void
444 85518602 : bitmap_tree_rotate_left (bitmap_element * &t)
445 : {
446 85518602 : bitmap_element *e = t->next;
447 85518602 : t->next = t->next->prev;
448 85518602 : e->prev = t;
449 85518602 : t = e;
450 85518602 : }
451 :
452 : static inline void
453 90935701 : bitmap_tree_rotate_right (bitmap_element * &t)
454 : {
455 90935701 : bitmap_element *e = t->prev;
456 90935701 : t->prev = t->prev->next;
457 90935701 : e->next = t;
458 90935701 : t = e;
459 90935701 : }
460 :
461 : static bitmap_element *
462 779963212 : bitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx)
463 : {
464 779963212 : bitmap_element N, *l, *r;
465 :
466 779963212 : if (t == NULL)
467 : return NULL;
468 :
469 779963212 : bitmap_usage *usage = NULL;
470 779963212 : if (GATHER_STATISTICS)
471 : usage = bitmap_mem_desc.get_descriptor_for_instance (head);
472 :
473 779963212 : N.prev = N.next = NULL;
474 779963212 : l = r = &N;
475 :
476 1287895938 : while (indx != t->indx)
477 : {
478 670079461 : if (GATHER_STATISTICS && usage)
479 : usage->m_search_iter++;
480 :
481 670079461 : if (indx < t->indx)
482 : {
483 345661936 : if (t->prev != NULL && indx < t->prev->indx)
484 90658429 : bitmap_tree_rotate_right (t);
485 345661936 : if (t->prev == NULL)
486 : break;
487 265688851 : bitmap_tree_link_right (t, r);
488 : }
489 324417525 : else if (indx > t->indx)
490 : {
491 324417525 : if (t->next != NULL && indx > t->next->indx)
492 85518602 : bitmap_tree_rotate_left (t);
493 324417525 : if (t->next == NULL)
494 : break;
495 242243875 : bitmap_tree_link_left (t, l);
496 : }
497 : }
498 :
499 779963212 : l->next = t->prev;
500 779963212 : r->prev = t->next;
501 779963212 : t->prev = N.next;
502 779963212 : t->next = N.prev;
503 779963212 : return t;
504 : }
505 :
506 : /* Link bitmap element E into the current bitmap splay tree. */
507 :
508 : static inline void
509 202656963 : bitmap_tree_link_element (bitmap head, bitmap_element *e)
510 : {
511 202656963 : if (head->first == NULL)
512 146563439 : e->prev = e->next = NULL;
513 : else
514 : {
515 56093524 : bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
516 56093524 : if (e->indx < t->indx)
517 : {
518 25081731 : e->prev = t->prev;
519 25081731 : e->next = t;
520 25081731 : t->prev = NULL;
521 : }
522 31011793 : else if (e->indx > t->indx)
523 : {
524 31011793 : e->next = t->next;
525 31011793 : e->prev = t;
526 31011793 : t->next = NULL;
527 : }
528 : else
529 0 : gcc_unreachable ();
530 : }
531 202656963 : head->first = e;
532 202656963 : head->current = e;
533 202656963 : head->indx = e->indx;
534 202656963 : }
535 :
536 : /* Unlink bitmap element E from the current bitmap splay tree,
537 : and return it to the freelist. */
538 :
539 : static void
540 105310229 : bitmap_tree_unlink_element (bitmap head, bitmap_element *e)
541 : {
542 105310229 : bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
543 :
544 105310229 : gcc_checking_assert (t == e);
545 :
546 105310229 : if (e->prev == NULL)
547 104570378 : t = e->next;
548 : else
549 : {
550 739851 : t = bitmap_tree_splay (head, e->prev, e->indx);
551 739851 : t->next = e->next;
552 : }
553 105310229 : head->first = t;
554 105310229 : head->current = t;
555 105310229 : head->indx = (t != NULL) ? t->indx : 0;
556 :
557 105310229 : bitmap_elem_to_freelist (head, e);
558 105310229 : }
559 :
560 : /* Return the element for INDX, or NULL if the element doesn't exist. */
561 :
562 : static inline bitmap_element *
563 3351576044 : bitmap_tree_find_element (bitmap head, unsigned int indx)
564 : {
565 3351576044 : if (head->current == NULL
566 2419148643 : || 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 502912407 : bitmap_usage *usage = NULL;
572 502912407 : 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 502912407 : if (GATHER_STATISTICS && usage)
578 : usage->m_nsearches++;
579 :
580 502912407 : bitmap_element *element = bitmap_tree_splay (head, head->first, indx);
581 502912407 : gcc_checking_assert (element != NULL);
582 502912407 : head->first = element;
583 502912407 : head->current = element;
584 502912407 : head->indx = element->indx;
585 502912407 : if (element->indx != indx)
586 105313360 : 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 61537033 : bitmap_tree_listify_from (bitmap head, bitmap_element *e)
598 : {
599 61537033 : 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 61537033 : erb = e->next;
604 61537033 : e->next = NULL;
605 61537033 : t = bitmap_tree_splay (head, head->first, e->indx);
606 61537033 : 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 61537033 : t = e->prev;
611 61537033 : head->first = t;
612 61537033 : head->current = t;
613 61537033 : head->indx = (t != NULL) ? t->indx : 0;
614 :
615 : /* Detach the tree from E, and re-attach the right branch of E. */
616 61537033 : e->prev = NULL;
617 61537033 : 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 61537033 : auto_vec<bitmap_element *, 32> stack;
627 61537033 : auto_vec<bitmap_element *, 32> sorted_elements;
628 61537033 : bitmap_element *n = e;
629 :
630 101256737 : while (true)
631 : {
632 264050507 : while (n != NULL)
633 : {
634 101256737 : stack.safe_push (n);
635 101256737 : n = n->prev;
636 : }
637 :
638 162793770 : if (stack.is_empty ())
639 : break;
640 :
641 101256737 : n = stack.pop ();
642 101256737 : sorted_elements.safe_push (n);
643 101256737 : n = n->next;
644 : }
645 :
646 61537033 : gcc_assert (sorted_elements[0] == e);
647 :
648 : bitmap_element *prev = NULL;
649 : unsigned ix;
650 162793770 : FOR_EACH_VEC_ELT (sorted_elements, ix, n)
651 : {
652 101256737 : if (prev != NULL)
653 39719704 : prev->next = n;
654 101256737 : n->prev = prev;
655 101256737 : n->next = NULL;
656 101256737 : prev = n;
657 : }
658 :
659 61537033 : return e;
660 61537033 : }
661 :
662 : /* Convert bitmap HEAD from splay-tree view to linked-list view. */
663 :
664 : void
665 10420609 : bitmap_list_view (bitmap head)
666 : {
667 10420609 : bitmap_element *ptr;
668 :
669 10420609 : gcc_assert (head->tree_form);
670 :
671 10420609 : ptr = head->first;
672 10420609 : if (ptr)
673 : {
674 8444137 : while (ptr->prev)
675 277272 : bitmap_tree_rotate_right (ptr);
676 8166865 : head->first = ptr;
677 8166865 : head->first = bitmap_tree_listify_from (head, ptr);
678 : }
679 :
680 10420609 : head->tree_form = false;
681 10420609 : if (!head->current)
682 : {
683 10420609 : head->current = head->first;
684 10420609 : head->indx = head->current ? head->current->indx : 0;
685 : }
686 10420609 : }
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 235405151 : bitmap_tree_view (bitmap head)
695 : {
696 235405151 : bitmap_element *ptr;
697 :
698 235405151 : gcc_assert (! head->tree_form);
699 :
700 235405151 : ptr = head->first;
701 243593062 : while (ptr)
702 : {
703 8187911 : ptr->prev = NULL;
704 8187911 : ptr = ptr->next;
705 : }
706 :
707 235405151 : head->tree_form = true;
708 235405151 : }
709 :
710 : /* Clear a bitmap by freeing all its elements. */
711 :
712 : void
713 13384810288 : bitmap_clear (bitmap head)
714 : {
715 13384810288 : if (head->first == NULL)
716 : return;
717 6483591090 : if (head->tree_form)
718 : {
719 : bitmap_element *e, *t;
720 70414371 : for (e = head->first; e->prev; e = e->prev)
721 : /* Loop to find the element with the smallest index. */ ;
722 53370168 : t = bitmap_tree_splay (head, head->first, e->indx);
723 53370168 : gcc_checking_assert (t == e);
724 53370168 : head->first = t;
725 : }
726 6483591090 : 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 342024681 : bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
734 : {
735 342024681 : if (!bit_obstack)
736 : {
737 47529711 : 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 330842178 : bit_obstack->elements = NULL;
747 330842178 : bit_obstack->heads = NULL;
748 330842178 : 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 341985835 : bitmap_obstack_release (bitmap_obstack *bit_obstack)
759 : {
760 341985835 : if (!bit_obstack)
761 : {
762 47508424 : if (--bitmap_default_obstack_depth)
763 : {
764 11182018 : gcc_assert (bitmap_default_obstack_depth > 0);
765 : return;
766 : }
767 : bit_obstack = &bitmap_default_obstack;
768 : }
769 :
770 330803817 : bit_obstack->elements = NULL;
771 330803817 : bit_obstack->heads = NULL;
772 330803817 : 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 3799307558 : bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL)
780 : {
781 3799307558 : bitmap map;
782 :
783 3799307558 : if (!bit_obstack)
784 : {
785 683594606 : gcc_assert (bitmap_default_obstack_depth > 0);
786 : bit_obstack = &bitmap_default_obstack;
787 : }
788 3799307558 : map = bit_obstack->heads;
789 3799307558 : if (map)
790 1249415282 : bit_obstack->heads = (class bitmap_head *) map->first;
791 : else
792 2549892276 : map = XOBNEW (&bit_obstack->obstack, bitmap_head);
793 3799307558 : bitmap_initialize (map, bit_obstack PASS_MEM_STAT);
794 :
795 3799307558 : if (GATHER_STATISTICS)
796 : register_overhead (map, sizeof (bitmap_head));
797 :
798 3799307558 : return map;
799 : }
800 :
801 : /* Create a new GCd bitmap. */
802 :
803 : bitmap
804 46133934 : bitmap_gc_alloc (ALONE_MEM_STAT_DECL)
805 : {
806 46133934 : bitmap map;
807 :
808 46133934 : map = ggc_alloc<bitmap_head> ();
809 46133934 : bitmap_initialize (map, NULL PASS_MEM_STAT);
810 :
811 46133934 : if (GATHER_STATISTICS)
812 : register_overhead (map, sizeof (bitmap_head));
813 :
814 46133934 : return map;
815 : }
816 :
817 : /* Release an obstack allocated bitmap. */
818 :
819 : void
820 2505875400 : bitmap_obstack_free (bitmap map)
821 : {
822 2505875400 : if (map)
823 : {
824 1414373425 : bitmap_clear (map);
825 1414373425 : map->first = (bitmap_element *) map->obstack->heads;
826 :
827 1414373425 : if (GATHER_STATISTICS)
828 : release_overhead (map, sizeof (bitmap_head), true);
829 :
830 1414373425 : map->obstack->heads = map;
831 : }
832 2505875400 : }
833 :
834 :
835 : /* Return nonzero if all bits in an element are zero. */
836 :
837 : static inline int
838 796539952 : bitmap_element_zerop (const bitmap_element *element)
839 : {
840 : #if BITMAP_ELEMENT_WORDS == 2
841 796539952 : 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 1980880761 : bitmap_copy (bitmap to, const_bitmap from)
857 : {
858 1980880761 : const bitmap_element *from_ptr;
859 1980880761 : bitmap_element *to_ptr = 0;
860 :
861 1980880761 : gcc_checking_assert (!to->tree_form && !from->tree_form);
862 :
863 1980880761 : bitmap_clear (to);
864 :
865 : /* Copy elements in forward direction one at a time. */
866 4352110821 : for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
867 : {
868 2371230060 : bitmap_element *to_elt = bitmap_element_allocate (to);
869 :
870 2371230060 : to_elt->indx = from_ptr->indx;
871 2371230060 : 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 2371230060 : if (to_ptr == 0)
877 : {
878 1568872493 : to->first = to->current = to_elt;
879 1568872493 : to->indx = from_ptr->indx;
880 1568872493 : to_elt->next = to_elt->prev = 0;
881 : }
882 : else
883 : {
884 802357567 : to_elt->prev = to_ptr;
885 802357567 : to_elt->next = 0;
886 802357567 : to_ptr->next = to_elt;
887 : }
888 :
889 2371230060 : to_ptr = to_elt;
890 : }
891 1980880761 : }
892 :
893 : /* Move a bitmap to another bitmap. */
894 :
895 : void
896 30885387 : bitmap_move (bitmap to, bitmap from)
897 : {
898 30885387 : gcc_assert (to->obstack == from->obstack);
899 :
900 30885387 : bitmap_clear (to);
901 :
902 30885387 : size_t sz = 0;
903 30885387 : 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 30885387 : *to = *from;
911 :
912 30885387 : if (GATHER_STATISTICS)
913 : release_overhead (from, sz, false);
914 30885387 : }
915 :
916 : /* Clear a single bit in a bitmap. Return true if the bit changed. */
917 :
918 : bool
919 25165122400 : bitmap_clear_bit (bitmap head, int bit)
920 : {
921 25165122400 : unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
922 25165122400 : bitmap_element *ptr;
923 :
924 25165122400 : if (!head->tree_form)
925 24343241107 : ptr = bitmap_list_find_element (head, indx);
926 : else
927 821881293 : ptr = bitmap_tree_find_element (head, indx);
928 25165122400 : if (ptr != 0)
929 : {
930 20396085636 : unsigned bit_num = bit % BITMAP_WORD_BITS;
931 20396085636 : unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
932 20396085636 : BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
933 20396085636 : bool res = (ptr->bits[word_num] & bit_val) != 0;
934 20396085636 : if (res)
935 : {
936 3519113100 : ptr->bits[word_num] &= ~bit_val;
937 : /* If we cleared the entire word, free up the element. */
938 3519113100 : if (!ptr->bits[word_num]
939 3519113100 : && bitmap_element_zerop (ptr))
940 : {
941 585178865 : if (!head->tree_form)
942 502808238 : bitmap_list_unlink_element (head, ptr);
943 : else
944 82370627 : bitmap_tree_unlink_element (head, ptr);
945 : }
946 : }
947 :
948 20396085636 : 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 36371582690 : bitmap_set_bit (bitmap head, int bit)
958 : {
959 36371582690 : unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
960 36371582690 : bitmap_element *ptr;
961 36371582690 : if (!head->tree_form)
962 34470654698 : ptr = bitmap_list_find_element (head, indx);
963 : else
964 1900927992 : ptr = bitmap_tree_find_element (head, indx);
965 36371582690 : unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
966 36371582690 : unsigned bit_num = bit % BITMAP_WORD_BITS;
967 36371582690 : BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
968 :
969 36371582690 : if (ptr != 0)
970 : {
971 28941465868 : bool res = (ptr->bits[word_num] & bit_val) == 0;
972 : /* Write back unconditionally to avoid branch mispredicts. */
973 28941465868 : ptr->bits[word_num] |= bit_val;
974 28941465868 : return res;
975 : }
976 :
977 7430116822 : ptr = bitmap_element_allocate (head);
978 7430116822 : ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
979 7430116822 : ptr->bits[word_num] = bit_val;
980 7430116822 : if (!head->tree_form)
981 7227592740 : bitmap_list_link_element (head, ptr);
982 : else
983 202524082 : 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 33728594119 : bitmap_bit_p (const_bitmap head, int bit)
991 : {
992 33728594119 : unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
993 33728594119 : const bitmap_element *ptr;
994 33728594119 : unsigned bit_num;
995 33728594119 : unsigned word_num;
996 :
997 33728594119 : if (!head->tree_form)
998 33114498967 : ptr = bitmap_list_find_element (const_cast<bitmap> (head), indx);
999 : else
1000 614095152 : ptr = bitmap_tree_find_element (const_cast<bitmap> (head), indx);
1001 33728594119 : if (ptr == 0)
1002 : return 0;
1003 :
1004 24312767302 : bit_num = bit % BITMAP_WORD_BITS;
1005 24312767302 : word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
1006 :
1007 24312767302 : 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 443574 : 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 443574 : gcc_checking_assert (pow2p_hwi (chunk_size));
1020 443574 : gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
1021 :
1022 : // Ensure chunk_value is within range of chunk_size bits.
1023 443574 : BITMAP_WORD max_value = (1 << chunk_size) - 1;
1024 443574 : gcc_checking_assert (chunk_value <= max_value);
1025 :
1026 443574 : unsigned bit = chunk * chunk_size;
1027 443574 : unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
1028 443574 : bitmap_element *ptr;
1029 443574 : if (!head->tree_form)
1030 64 : ptr = bitmap_list_find_element (head, indx);
1031 : else
1032 443510 : ptr = bitmap_tree_find_element (head, indx);
1033 443574 : unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
1034 443574 : unsigned bit_num = bit % BITMAP_WORD_BITS;
1035 443574 : BITMAP_WORD bit_val = chunk_value << bit_num;
1036 443574 : BITMAP_WORD mask = ~(max_value << bit_num);
1037 :
1038 443574 : if (ptr != 0)
1039 : {
1040 310681 : ptr->bits[word_num] &= mask;
1041 310681 : ptr->bits[word_num] |= bit_val;
1042 310681 : return;
1043 : }
1044 :
1045 132893 : ptr = bitmap_element_allocate (head);
1046 132893 : ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
1047 132893 : ptr->bits[word_num] = bit_val;
1048 132893 : if (!head->tree_form)
1049 12 : bitmap_list_link_element (head, ptr);
1050 : else
1051 132881 : 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 14228353 : 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 14228353 : gcc_checking_assert (pow2p_hwi (chunk_size));
1064 14228353 : gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
1065 :
1066 14228353 : BITMAP_WORD max_value = (1 << chunk_size) - 1;
1067 14228353 : unsigned bit = chunk * chunk_size;
1068 14228353 : unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
1069 14228353 : const bitmap_element *ptr;
1070 14228353 : unsigned bit_num;
1071 14228353 : unsigned word_num;
1072 :
1073 14228353 : if (!head->tree_form)
1074 256 : ptr = bitmap_list_find_element (const_cast<bitmap> (head), indx);
1075 : else
1076 14228097 : ptr = bitmap_tree_find_element (const_cast<bitmap> (head), indx);
1077 14228353 : if (ptr == 0)
1078 : return 0;
1079 :
1080 5312335 : bit_num = bit % BITMAP_WORD_BITS;
1081 5312335 : word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
1082 :
1083 : // Return 4 bits.
1084 5312335 : 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 65910819 : bitmap_count_bits_in_word (const BITMAP_WORD *bits)
1117 : {
1118 65910819 : unsigned long count = 0;
1119 :
1120 200581956 : 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 133721304 : count += __builtin_popcountl (bits[ix]);
1126 : #else
1127 : count += bitmap_popcount (bits[ix]);
1128 : #endif
1129 : }
1130 66860652 : return count;
1131 : }
1132 :
1133 : /* Count the number of bits set in the bitmap, and return it. */
1134 :
1135 : unsigned long
1136 124845093 : bitmap_count_bits (const_bitmap a)
1137 : {
1138 124845093 : unsigned long count = 0;
1139 124845093 : const bitmap_element *elt;
1140 :
1141 124845093 : gcc_checking_assert (!a->tree_form);
1142 190606214 : for (elt = a->first; elt; elt = elt->next)
1143 131522242 : count += bitmap_count_bits_in_word (elt->bits);
1144 :
1145 124845093 : return count;
1146 : }
1147 :
1148 : /* Count the number of unique bits set in A and B and return it. */
1149 :
1150 : unsigned long
1151 799268 : bitmap_count_unique_bits (const_bitmap a, const_bitmap b)
1152 : {
1153 799268 : unsigned long count = 0;
1154 799268 : const bitmap_element *elt_a, *elt_b;
1155 :
1156 1898799 : 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 1099531 : if (elt_a->indx < elt_b->indx)
1162 : {
1163 60837 : count += bitmap_count_bits_in_word (elt_a->bits);
1164 60837 : elt_a = elt_a->next;
1165 : }
1166 1038694 : else if (elt_b->indx < elt_a->indx)
1167 : {
1168 88861 : count += bitmap_count_bits_in_word (elt_b->bits);
1169 88861 : elt_b = elt_b->next;
1170 : }
1171 : else
1172 : {
1173 : BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
1174 2849499 : for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1175 1899666 : bits[ix] = elt_a->bits[ix] | elt_b->bits[ix];
1176 949833 : count += bitmap_count_bits_in_word (bits);
1177 949833 : elt_a = elt_a->next;
1178 949833 : elt_b = elt_b->next;
1179 : }
1180 : }
1181 799268 : return count;
1182 : }
1183 :
1184 : /* Return true if the bitmap has a single bit set. Otherwise return
1185 : false. */
1186 :
1187 : bool
1188 2641198 : bitmap_single_bit_set_p (const_bitmap a)
1189 : {
1190 2641198 : unsigned long count = 0;
1191 2641198 : const bitmap_element *elt;
1192 2641198 : unsigned ix;
1193 :
1194 2641198 : if (bitmap_empty_p (a))
1195 : return false;
1196 :
1197 2639820 : 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 2639820 : if (elt->next != NULL
1202 273279 : && (!a->tree_form || elt->prev != NULL))
1203 : return false;
1204 :
1205 5377520 : 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 4013173 : count += __builtin_popcountl (elt->bits[ix]);
1211 : #else
1212 : count += bitmap_popcount (elt->bits[ix]);
1213 : #endif
1214 4013173 : if (count > 1)
1215 : return false;
1216 : }
1217 :
1218 1364347 : 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 716937461 : bitmap_first_set_bit_worker (bitmap a, bool clear)
1227 : {
1228 716937461 : bitmap_element *elt = a->first;
1229 716937461 : unsigned bit_no;
1230 716937461 : BITMAP_WORD word;
1231 716937461 : unsigned ix;
1232 :
1233 716937461 : gcc_checking_assert (elt);
1234 :
1235 716937461 : if (a->tree_form)
1236 310027473 : while (elt->prev)
1237 : elt = elt->prev;
1238 :
1239 716937461 : bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
1240 905281023 : for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1241 : {
1242 905281023 : word = elt->bits[ix];
1243 905281023 : if (word)
1244 716937461 : goto found_bit;
1245 : }
1246 0 : gcc_unreachable ();
1247 716937461 : found_bit:
1248 716937461 : bit_no += ix * BITMAP_WORD_BITS;
1249 :
1250 : #if GCC_VERSION >= 3004
1251 716937461 : gcc_assert (sizeof (long) == sizeof (word));
1252 716937461 : 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 716937461 : if (clear)
1277 : {
1278 224044367 : elt->bits[ix] &= ~((BITMAP_WORD) 1 << (bit_no % BITMAP_WORD_BITS));
1279 : /* If we cleared the entire word, free up the element. */
1280 224044367 : if (!elt->bits[ix]
1281 224044367 : && bitmap_element_zerop (elt))
1282 : {
1283 46167560 : if (!a->tree_form)
1284 23227958 : bitmap_list_unlink_element (a, elt);
1285 : else
1286 22939602 : bitmap_tree_unlink_element (a, elt);
1287 : }
1288 : }
1289 :
1290 716937461 : 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 492893094 : bitmap_first_set_bit (const_bitmap a)
1298 : {
1299 492893094 : 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 224044367 : bitmap_clear_first_set_bit (bitmap a)
1307 : {
1308 224044367 : return bitmap_first_set_bit_worker (a, true);
1309 : }
1310 :
1311 : /* Return the bit number of the first set bit in the bitmap. The
1312 : bitmap must be non-empty. */
1313 :
1314 : unsigned
1315 0 : bitmap_last_set_bit (const_bitmap a)
1316 : {
1317 0 : const bitmap_element *elt;
1318 0 : unsigned bit_no;
1319 0 : BITMAP_WORD word;
1320 0 : int ix;
1321 :
1322 0 : if (a->tree_form)
1323 0 : elt = a->first;
1324 : else
1325 0 : elt = a->current ? a->current : a->first;
1326 0 : gcc_checking_assert (elt);
1327 :
1328 0 : while (elt->next)
1329 : elt = elt->next;
1330 :
1331 0 : bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
1332 0 : for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 1; ix--)
1333 : {
1334 0 : word = elt->bits[ix];
1335 0 : if (word)
1336 0 : goto found_bit;
1337 : }
1338 0 : gcc_assert (elt->bits[ix] != 0);
1339 0 : found_bit:
1340 0 : bit_no += ix * BITMAP_WORD_BITS;
1341 : #if GCC_VERSION >= 3004
1342 0 : gcc_assert (sizeof (long) == sizeof (word));
1343 0 : bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1;
1344 : #else
1345 : /* Hopefully this is a twos-complement host... */
1346 : BITMAP_WORD x = word;
1347 : x |= (x >> 1);
1348 : x |= (x >> 2);
1349 : x |= (x >> 4);
1350 : x |= (x >> 8);
1351 : x |= (x >> 16);
1352 : #if BITMAP_WORD_BITS > 32
1353 : x |= (x >> 32);
1354 : #endif
1355 : bit_no += bitmap_popcount (x) - 1;
1356 : #endif
1357 :
1358 0 : return bit_no;
1359 : }
1360 :
1361 :
1362 : /* DST = A & B. */
1363 :
1364 : void
1365 716788087 : bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
1366 : {
1367 716788087 : bitmap_element *dst_elt = dst->first;
1368 716788087 : const bitmap_element *a_elt = a->first;
1369 716788087 : const bitmap_element *b_elt = b->first;
1370 716788087 : bitmap_element *dst_prev = NULL;
1371 :
1372 716788087 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
1373 716788087 : gcc_assert (dst != a && dst != b);
1374 :
1375 716788087 : if (a == b)
1376 : {
1377 0 : bitmap_copy (dst, a);
1378 0 : return;
1379 : }
1380 :
1381 1690169684 : while (a_elt && b_elt)
1382 : {
1383 973381597 : if (a_elt->indx < b_elt->indx)
1384 24914213 : a_elt = a_elt->next;
1385 948467384 : else if (b_elt->indx < a_elt->indx)
1386 181969724 : b_elt = b_elt->next;
1387 : else
1388 : {
1389 : /* Matching elts, generate A & B. */
1390 766497660 : unsigned ix;
1391 766497660 : BITMAP_WORD ior = 0;
1392 :
1393 766497660 : if (!dst_elt)
1394 247356519 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
1395 : a_elt->indx);
1396 : else
1397 519141141 : dst_elt->indx = a_elt->indx;
1398 2299492980 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1399 : {
1400 1532995320 : BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
1401 :
1402 1532995320 : dst_elt->bits[ix] = r;
1403 1532995320 : ior |= r;
1404 : }
1405 766497660 : if (ior)
1406 : {
1407 459489069 : dst_prev = dst_elt;
1408 459489069 : dst_elt = dst_elt->next;
1409 : }
1410 766497660 : a_elt = a_elt->next;
1411 766497660 : b_elt = b_elt->next;
1412 : }
1413 : }
1414 : /* Ensure that dst->current is valid. */
1415 716788087 : dst->current = dst->first;
1416 716788087 : bitmap_elt_clear_from (dst, dst_elt);
1417 716788087 : gcc_checking_assert (!dst->current == !dst->first);
1418 716788087 : if (dst->current)
1419 395663520 : dst->indx = dst->current->indx;
1420 : }
1421 :
1422 : /* A &= B. Return true if A changed. */
1423 :
1424 : bool
1425 1029046767 : bitmap_and_into (bitmap a, const_bitmap b)
1426 : {
1427 1029046767 : bitmap_element *a_elt = a->first;
1428 1029046767 : const bitmap_element *b_elt = b->first;
1429 1029046767 : bitmap_element *next;
1430 1029046767 : bool changed = false;
1431 :
1432 1029046767 : gcc_checking_assert (!a->tree_form && !b->tree_form);
1433 :
1434 1029046767 : if (a == b)
1435 : return false;
1436 :
1437 3013455923 : while (a_elt && b_elt)
1438 : {
1439 1984409156 : if (a_elt->indx < b_elt->indx)
1440 : {
1441 43591258 : next = a_elt->next;
1442 43591258 : bitmap_list_unlink_element (a, a_elt);
1443 43591258 : a_elt = next;
1444 43591258 : changed = true;
1445 : }
1446 1940817898 : else if (b_elt->indx < a_elt->indx)
1447 53718894 : b_elt = b_elt->next;
1448 : else
1449 : {
1450 : /* Matching elts, generate A &= B. */
1451 : unsigned ix;
1452 : BITMAP_WORD ior = 0;
1453 :
1454 5661297012 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1455 : {
1456 3774198008 : BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
1457 3774198008 : if (a_elt->bits[ix] != r)
1458 377907123 : changed = true;
1459 3774198008 : a_elt->bits[ix] = r;
1460 3774198008 : ior |= r;
1461 : }
1462 1887099004 : next = a_elt->next;
1463 1887099004 : if (!ior)
1464 6876035 : bitmap_list_unlink_element (a, a_elt);
1465 1887099004 : a_elt = next;
1466 1887099004 : b_elt = b_elt->next;
1467 : }
1468 : }
1469 :
1470 1029046767 : if (a_elt)
1471 : {
1472 56031435 : changed = true;
1473 56031435 : bitmap_elt_clear_from (a, a_elt);
1474 : }
1475 :
1476 1029046767 : 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 3459049388 : bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
1489 : const bitmap_element *src_elt, bool changed)
1490 : {
1491 3459049388 : if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
1492 : {
1493 : unsigned ix;
1494 :
1495 284764404 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1496 189842936 : if (src_elt->bits[ix] != dst_elt->bits[ix])
1497 : {
1498 26307354 : dst_elt->bits[ix] = src_elt->bits[ix];
1499 26307354 : changed = true;
1500 : }
1501 : }
1502 : else
1503 : {
1504 3461281886 : changed = true;
1505 3297050269 : if (!dst_elt)
1506 3199896303 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
1507 3199896303 : src_elt->indx);
1508 : else
1509 164231617 : dst_elt->indx = src_elt->indx;
1510 3364127920 : memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
1511 : }
1512 3459049388 : return changed;
1513 : }
1514 :
1515 :
1516 :
1517 : /* DST = A & ~B */
1518 :
1519 : bool
1520 190034579 : bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
1521 : {
1522 190034579 : bitmap_element *dst_elt = dst->first;
1523 190034579 : const bitmap_element *a_elt = a->first;
1524 190034579 : const bitmap_element *b_elt = b->first;
1525 190034579 : bitmap_element *dst_prev = NULL;
1526 190034579 : bitmap_element **dst_prev_pnext = &dst->first;
1527 190034579 : bool changed = false;
1528 :
1529 190034579 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
1530 190034579 : gcc_assert (dst != a && dst != b);
1531 :
1532 190034579 : if (a == b)
1533 : {
1534 0 : changed = !bitmap_empty_p (dst);
1535 0 : bitmap_clear (dst);
1536 0 : return changed;
1537 : }
1538 :
1539 551572509 : while (a_elt)
1540 : {
1541 376732998 : while (b_elt && b_elt->indx < a_elt->indx)
1542 15195068 : b_elt = b_elt->next;
1543 :
1544 361537930 : if (!b_elt || b_elt->indx > a_elt->indx)
1545 : {
1546 192924469 : changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
1547 192924469 : dst_prev = *dst_prev_pnext;
1548 192924469 : dst_prev_pnext = &dst_prev->next;
1549 192924469 : dst_elt = *dst_prev_pnext;
1550 192924469 : a_elt = a_elt->next;
1551 : }
1552 :
1553 : else
1554 : {
1555 : /* Matching elts, generate A & ~B. */
1556 168613461 : unsigned ix;
1557 168613461 : BITMAP_WORD ior = 0;
1558 :
1559 168613461 : if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1560 : {
1561 131718729 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1562 : {
1563 87812486 : BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1564 :
1565 87812486 : if (dst_elt->bits[ix] != r)
1566 : {
1567 29711012 : changed = true;
1568 29711012 : dst_elt->bits[ix] = r;
1569 : }
1570 87812486 : ior |= r;
1571 : }
1572 : }
1573 : else
1574 : {
1575 108107785 : bool new_element;
1576 124707218 : if (!dst_elt || dst_elt->indx > a_elt->indx)
1577 : {
1578 123507835 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
1579 : a_elt->indx);
1580 123507835 : new_element = true;
1581 : }
1582 : else
1583 : {
1584 1199383 : dst_elt->indx = a_elt->indx;
1585 1199383 : new_element = false;
1586 : }
1587 :
1588 374121654 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1589 : {
1590 249414436 : BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1591 :
1592 249414436 : dst_elt->bits[ix] = r;
1593 249414436 : ior |= r;
1594 : }
1595 :
1596 124707218 : if (ior)
1597 : changed = true;
1598 : else
1599 : {
1600 43224552 : changed |= !new_element;
1601 43224552 : bitmap_list_unlink_element (dst, dst_elt);
1602 43224552 : dst_elt = *dst_prev_pnext;
1603 : }
1604 : }
1605 :
1606 87130795 : if (ior)
1607 : {
1608 124470801 : dst_prev = *dst_prev_pnext;
1609 124470801 : dst_prev_pnext = &dst_prev->next;
1610 124470801 : dst_elt = *dst_prev_pnext;
1611 : }
1612 168613461 : a_elt = a_elt->next;
1613 168613461 : b_elt = b_elt->next;
1614 : }
1615 : }
1616 :
1617 : /* Ensure that dst->current is valid. */
1618 190034579 : dst->current = dst->first;
1619 :
1620 190034579 : if (dst_elt)
1621 : {
1622 1767139 : changed = true;
1623 1767139 : bitmap_elt_clear_from (dst, dst_elt);
1624 : }
1625 190034579 : gcc_checking_assert (!dst->current == !dst->first);
1626 190034579 : if (dst->current)
1627 143223431 : dst->indx = dst->current->indx;
1628 :
1629 : return changed;
1630 : }
1631 :
1632 : /* A &= ~B. Returns true if A changes */
1633 :
1634 : bool
1635 414982446 : bitmap_and_compl_into (bitmap a, const_bitmap b)
1636 : {
1637 414982446 : bitmap_element *a_elt = a->first;
1638 414982446 : const bitmap_element *b_elt = b->first;
1639 414982446 : bitmap_element *next;
1640 414982446 : BITMAP_WORD changed = 0;
1641 :
1642 414982446 : gcc_checking_assert (!a->tree_form && !b->tree_form);
1643 :
1644 414982446 : 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 1228888388 : while (a_elt && b_elt)
1656 : {
1657 813905942 : if (a_elt->indx < b_elt->indx)
1658 169542615 : a_elt = a_elt->next;
1659 644363327 : else if (b_elt->indx < a_elt->indx)
1660 343382470 : b_elt = b_elt->next;
1661 : else
1662 : {
1663 : /* Matching elts, generate A &= ~B. */
1664 : unsigned ix;
1665 : BITMAP_WORD ior = 0;
1666 :
1667 902942571 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1668 : {
1669 601961714 : BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1670 601961714 : BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
1671 :
1672 601961714 : a_elt->bits[ix] = r;
1673 601961714 : changed |= cleared;
1674 601961714 : ior |= r;
1675 : }
1676 300980857 : next = a_elt->next;
1677 300980857 : if (!ior)
1678 13711136 : bitmap_list_unlink_element (a, a_elt);
1679 300980857 : a_elt = next;
1680 300980857 : b_elt = b_elt->next;
1681 : }
1682 : }
1683 414982446 : gcc_checking_assert (!a->current == !a->first
1684 : && (!a->current || a->indx == a->current->indx));
1685 414982446 : return changed != 0;
1686 : }
1687 :
1688 : /* Set COUNT bits from START in HEAD. */
1689 : void
1690 1644286246 : bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
1691 : {
1692 1644286246 : unsigned int first_index, end_bit_plus1, last_index;
1693 1644286246 : bitmap_element *elt, *elt_prev;
1694 1644286246 : unsigned int i;
1695 :
1696 1644286246 : gcc_checking_assert (!head->tree_form);
1697 :
1698 1644286246 : if (!count)
1699 : return;
1700 :
1701 1330459416 : if (count == 1)
1702 : {
1703 594576451 : bitmap_set_bit (head, start);
1704 594576451 : return;
1705 : }
1706 :
1707 735882965 : first_index = start / BITMAP_ELEMENT_ALL_BITS;
1708 735882965 : end_bit_plus1 = start + count;
1709 735882965 : last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1710 735882965 : 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 735882965 : if (!elt)
1717 : {
1718 140167980 : elt = bitmap_element_allocate (head);
1719 140167980 : elt->indx = first_index;
1720 140167980 : bitmap_list_link_element (head, elt);
1721 : }
1722 :
1723 735882965 : gcc_checking_assert (elt->indx == first_index);
1724 735882965 : elt_prev = elt->prev;
1725 1529949579 : for (i = first_index; i <= last_index; i++)
1726 : {
1727 794066614 : unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
1728 794066614 : unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1729 :
1730 794066614 : unsigned int first_word_to_mod;
1731 794066614 : BITMAP_WORD first_mask;
1732 794066614 : unsigned int last_word_to_mod;
1733 794066614 : BITMAP_WORD last_mask;
1734 794066614 : unsigned int ix;
1735 :
1736 794066614 : if (!elt || elt->indx != i)
1737 57933159 : elt = bitmap_list_insert_element_after (head, elt_prev, i);
1738 :
1739 794066614 : if (elt_start_bit <= start)
1740 : {
1741 : /* The first bit to turn on is somewhere inside this
1742 : elt. */
1743 735882965 : first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1744 :
1745 : /* This mask should have 1s in all bits >= start position. */
1746 735882965 : first_mask =
1747 735882965 : (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1748 735882965 : 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 794066614 : 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 731096601 : last_word_to_mod =
1767 731096601 : (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1768 :
1769 : /* The last mask should have 1s below the end bit. */
1770 731096601 : last_mask =
1771 731096601 : (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
1772 : }
1773 :
1774 794066614 : if (first_word_to_mod == last_word_to_mod)
1775 : {
1776 721734607 : BITMAP_WORD mask = first_mask & last_mask;
1777 721734607 : elt->bits[first_word_to_mod] |= mask;
1778 : }
1779 : else
1780 : {
1781 72332007 : elt->bits[first_word_to_mod] |= first_mask;
1782 72332007 : 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 72332007 : elt->bits[last_word_to_mod] |= last_mask;
1786 : }
1787 :
1788 794066614 : elt_prev = elt;
1789 794066614 : elt = elt->next;
1790 : }
1791 :
1792 735882965 : head->current = elt ? elt : elt_prev;
1793 735882965 : head->indx = head->current->indx;
1794 : }
1795 :
1796 : /* Clear COUNT bits from START in HEAD. */
1797 : void
1798 2839137662 : bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
1799 : {
1800 2839137662 : unsigned int first_index, end_bit_plus1, last_index;
1801 2839137662 : bitmap_element *elt;
1802 :
1803 2839137662 : gcc_checking_assert (!head->tree_form);
1804 :
1805 2839137662 : if (!count)
1806 : return;
1807 :
1808 2839137257 : if (count == 1)
1809 : {
1810 408442439 : bitmap_clear_bit (head, start);
1811 408442439 : return;
1812 : }
1813 :
1814 2430694818 : first_index = start / BITMAP_ELEMENT_ALL_BITS;
1815 2430694818 : end_bit_plus1 = start + count;
1816 2430694818 : last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1817 2430694818 : 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 2430694818 : if (!elt)
1823 : {
1824 1669511676 : if (head->current)
1825 : {
1826 1613772709 : if (head->indx < first_index)
1827 : {
1828 1142992794 : elt = head->current->next;
1829 1142992794 : if (!elt)
1830 : return;
1831 : }
1832 : else
1833 : elt = head->current;
1834 : }
1835 : else
1836 : return;
1837 : }
1838 :
1839 2708178858 : while (elt && (elt->indx <= last_index))
1840 : {
1841 922666516 : bitmap_element * next_elt = elt->next;
1842 922666516 : unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
1843 922666516 : unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1844 :
1845 :
1846 922666516 : 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 53094914 : bitmap_list_unlink_element (head, elt);
1849 : else
1850 : {
1851 : /* Going to have to knock out some bits in this elt. */
1852 869571602 : unsigned int first_word_to_mod;
1853 869571602 : BITMAP_WORD first_mask;
1854 869571602 : unsigned int last_word_to_mod;
1855 869571602 : BITMAP_WORD last_mask;
1856 869571602 : unsigned int i;
1857 869571602 : bool clear = true;
1858 :
1859 869571602 : if (elt_start_bit <= start)
1860 : {
1861 : /* The first bit to turn off is somewhere inside this
1862 : elt. */
1863 759122652 : first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1864 :
1865 : /* This mask should have 1s in all bits >= start position. */
1866 759122652 : first_mask =
1867 759122652 : (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1868 759122652 : 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 869571602 : 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 721255259 : last_word_to_mod =
1889 721255259 : (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1890 :
1891 : /* The last mask should have 1s below the end bit. */
1892 721255259 : last_mask =
1893 721255259 : (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
1894 : }
1895 :
1896 :
1897 869571602 : if (first_word_to_mod == last_word_to_mod)
1898 : {
1899 721795972 : BITMAP_WORD mask = first_mask & last_mask;
1900 721795972 : elt->bits[first_word_to_mod] &= ~mask;
1901 : }
1902 : else
1903 : {
1904 147775630 : elt->bits[first_word_to_mod] &= ~first_mask;
1905 147775630 : 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 147775630 : elt->bits[last_word_to_mod] &= ~last_mask;
1909 : }
1910 1173089708 : for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1911 1130229615 : if (elt->bits[i])
1912 : {
1913 : clear = false;
1914 : break;
1915 : }
1916 : /* Check to see if there are any bits left. */
1917 869571602 : if (clear)
1918 42860093 : bitmap_list_unlink_element (head, elt);
1919 : }
1920 : elt = next_elt;
1921 : }
1922 :
1923 1785512342 : if (elt)
1924 : {
1925 1419081806 : head->current = elt;
1926 1419081806 : 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 7347820103 : 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 7347820103 : gcc_assert (a_elt || b_elt);
2011 :
2012 7347820103 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2013 : {
2014 : /* Matching elts, generate A | B. */
2015 4189848074 : unsigned ix;
2016 :
2017 4189848074 : if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
2018 : {
2019 10956974475 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2020 : {
2021 7304649650 : BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
2022 7304649650 : if (r != dst_elt->bits[ix])
2023 : {
2024 1221980090 : dst_elt->bits[ix] = r;
2025 1221980090 : changed = true;
2026 : }
2027 : }
2028 : }
2029 : else
2030 : {
2031 939673198 : changed = true;
2032 536748377 : if (!dst_elt)
2033 134598428 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
2034 : a_elt->indx);
2035 : else
2036 402924821 : dst_elt->indx = a_elt->indx;
2037 1612569747 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2038 : {
2039 1075046498 : BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
2040 1075046498 : dst_elt->bits[ix] = r;
2041 : }
2042 : }
2043 : }
2044 : else
2045 : {
2046 : /* Copy a single element. */
2047 2922087077 : const bitmap_element *src;
2048 :
2049 3157972029 : if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
2050 : src = a_elt;
2051 : else
2052 192419986 : src = b_elt;
2053 :
2054 3114507063 : gcc_checking_assert (src);
2055 3157972029 : changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
2056 : }
2057 7347820103 : return changed;
2058 : }
2059 :
2060 :
2061 : /* DST = A | B. Return true if DST changes. */
2062 :
2063 : bool
2064 337236444 : bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
2065 : {
2066 337236444 : bitmap_element *dst_elt = dst->first;
2067 337236444 : const bitmap_element *a_elt = a->first;
2068 337236444 : const bitmap_element *b_elt = b->first;
2069 337236444 : bitmap_element *dst_prev = NULL;
2070 337236444 : bitmap_element **dst_prev_pnext = &dst->first;
2071 337236444 : bool changed = false;
2072 :
2073 337236444 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
2074 337236444 : gcc_assert (dst != a && dst != b);
2075 :
2076 942646842 : while (a_elt || b_elt)
2077 : {
2078 605410398 : changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
2079 :
2080 605410398 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2081 : {
2082 208468810 : a_elt = a_elt->next;
2083 208468810 : b_elt = b_elt->next;
2084 : }
2085 : else
2086 : {
2087 396941588 : if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
2088 32912173 : a_elt = a_elt->next;
2089 364029415 : else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
2090 364029415 : b_elt = b_elt->next;
2091 : }
2092 :
2093 605410398 : dst_prev = *dst_prev_pnext;
2094 605410398 : dst_prev_pnext = &dst_prev->next;
2095 605410398 : dst_elt = *dst_prev_pnext;
2096 : }
2097 :
2098 337236444 : if (dst_elt)
2099 : {
2100 7976 : changed = true;
2101 : /* Ensure that dst->current is valid. */
2102 7976 : dst->current = dst->first;
2103 7976 : bitmap_elt_clear_from (dst, dst_elt);
2104 : }
2105 337236444 : gcc_checking_assert (!dst->current == !dst->first);
2106 337236444 : if (dst->current)
2107 335944966 : dst->indx = dst->current->indx;
2108 337236444 : return changed;
2109 : }
2110 :
2111 : /* A |= B. Return true if A changes. */
2112 :
2113 : bool
2114 4634691670 : bitmap_ior_into (bitmap a, const_bitmap b)
2115 : {
2116 4634691670 : bitmap_element *a_elt = a->first;
2117 4634691670 : const bitmap_element *b_elt = b->first;
2118 4634691670 : bitmap_element *a_prev = NULL;
2119 4634691670 : bitmap_element **a_prev_pnext = &a->first;
2120 4634691670 : bool changed = false;
2121 :
2122 4634691670 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2123 4634691670 : if (a == b)
2124 : return false;
2125 :
2126 11141211352 : while (b_elt)
2127 : {
2128 : /* If A lags behind B, just advance it. */
2129 6506523808 : if (!a_elt || a_elt->indx == b_elt->indx)
2130 : {
2131 5625381552 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
2132 5625381552 : b_elt = b_elt->next;
2133 : }
2134 881142256 : else if (a_elt->indx > b_elt->indx)
2135 : {
2136 106882481 : changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);
2137 106882481 : b_elt = b_elt->next;
2138 : }
2139 :
2140 6506523808 : a_prev = *a_prev_pnext;
2141 6506523808 : a_prev_pnext = &a_prev->next;
2142 6506523808 : a_elt = *a_prev_pnext;
2143 : }
2144 :
2145 4634687544 : gcc_checking_assert (!a->current == !a->first);
2146 4634687544 : if (a->current)
2147 4306492746 : 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 11536593 : bitmap_ior_into_and_free (bitmap a, bitmap *b_)
2156 : {
2157 11536593 : bitmap b = *b_;
2158 11536593 : bitmap_element *a_elt = a->first;
2159 11536593 : bitmap_element *b_elt = b->first;
2160 11536593 : bitmap_element *a_prev = NULL;
2161 11536593 : bitmap_element **a_prev_pnext = &a->first;
2162 11536593 : bool changed = false;
2163 :
2164 11536593 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2165 11536593 : gcc_assert (a->obstack == b->obstack);
2166 11536593 : if (a == b)
2167 : return false;
2168 :
2169 38539416 : while (b_elt)
2170 : {
2171 : /* If A lags behind B, just advance it. */
2172 27002823 : if (!a_elt || a_elt->indx == b_elt->indx)
2173 : {
2174 16832521 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
2175 16832521 : b_elt = b_elt->next;
2176 : }
2177 10170302 : else if (a_elt->indx > b_elt->indx)
2178 : {
2179 4538529 : bitmap_element *b_elt_next = b_elt->next;
2180 4538529 : bitmap_list_unlink_element (b, b_elt, false);
2181 4538529 : bitmap_list_insert_element_after (a, a_prev, b_elt->indx, b_elt);
2182 4538529 : b_elt = b_elt_next;
2183 : }
2184 :
2185 27002823 : a_prev = *a_prev_pnext;
2186 27002823 : a_prev_pnext = &a_prev->next;
2187 27002823 : a_elt = *a_prev_pnext;
2188 : }
2189 :
2190 11536593 : gcc_checking_assert (!a->current == !a->first);
2191 11536593 : if (a->current)
2192 11536593 : a->indx = a->current->indx;
2193 :
2194 11536593 : if (b->obstack)
2195 11536593 : 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 480990854 : bitmap_equal_p (const_bitmap a, const_bitmap b)
2348 : {
2349 480990854 : const bitmap_element *a_elt;
2350 480990854 : const bitmap_element *b_elt;
2351 480990854 : unsigned ix;
2352 :
2353 480990854 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2354 :
2355 480990854 : for (a_elt = a->first, b_elt = b->first;
2356 989956490 : a_elt && b_elt;
2357 508965636 : a_elt = a_elt->next, b_elt = b_elt->next)
2358 : {
2359 622478692 : if (a_elt->indx != b_elt->indx)
2360 : return false;
2361 1612736790 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2362 1103771154 : if (a_elt->bits[ix] != b_elt->bits[ix])
2363 : return false;
2364 : }
2365 367477798 : return !a_elt && !b_elt;
2366 : }
2367 :
2368 : /* Return true if A AND B is not empty. */
2369 :
2370 : bool
2371 378232101 : bitmap_intersect_p (const_bitmap a, const_bitmap b)
2372 : {
2373 378232101 : const bitmap_element *a_elt;
2374 378232101 : const bitmap_element *b_elt;
2375 378232101 : unsigned ix;
2376 :
2377 378232101 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2378 :
2379 378232101 : for (a_elt = a->first, b_elt = b->first;
2380 753826295 : a_elt && b_elt;)
2381 : {
2382 463272483 : if (a_elt->indx < b_elt->indx)
2383 172025012 : a_elt = a_elt->next;
2384 291247471 : else if (b_elt->indx < a_elt->indx)
2385 73101856 : b_elt = b_elt->next;
2386 : else
2387 : {
2388 509694370 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2389 379227044 : if (a_elt->bits[ix] & b_elt->bits[ix])
2390 : return true;
2391 130467326 : a_elt = a_elt->next;
2392 130467326 : 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 856595646 : bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
2433 : {
2434 856595646 : bool changed = false;
2435 :
2436 856595646 : bitmap_element *dst_elt = dst->first;
2437 856595646 : const bitmap_element *a_elt = a->first;
2438 856595646 : const bitmap_element *b_elt = b->first;
2439 856595646 : const bitmap_element *kill_elt = kill->first;
2440 856595646 : bitmap_element *dst_prev = NULL;
2441 856595646 : bitmap_element **dst_prev_pnext = &dst->first;
2442 :
2443 856595646 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form
2444 : && !kill->tree_form);
2445 856595646 : gcc_assert (dst != a && dst != b && dst != kill);
2446 :
2447 : /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
2448 856595646 : if (b == kill || bitmap_empty_p (b))
2449 : {
2450 65474280 : changed = !bitmap_equal_p (dst, a);
2451 65474280 : if (changed)
2452 4022804 : bitmap_copy (dst, a);
2453 65474280 : return changed;
2454 : }
2455 791121366 : if (bitmap_empty_p (kill))
2456 287910373 : return bitmap_ior (dst, a, b);
2457 503210993 : if (bitmap_empty_p (a))
2458 35812867 : return bitmap_and_compl (dst, b, kill);
2459 :
2460 1554751410 : while (a_elt || b_elt)
2461 : {
2462 1087353284 : bool new_element = false;
2463 :
2464 1087353284 : if (b_elt)
2465 1083586773 : while (kill_elt && kill_elt->indx < b_elt->indx)
2466 25633835 : kill_elt = kill_elt->next;
2467 :
2468 1087353284 : if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
2469 597562201 : && (!a_elt || a_elt->indx >= b_elt->indx))
2470 : {
2471 591421652 : bitmap_element tmp_elt;
2472 591421652 : unsigned ix;
2473 :
2474 591421652 : BITMAP_WORD ior = 0;
2475 591421652 : tmp_elt.indx = b_elt->indx;
2476 1774264956 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2477 : {
2478 1182843304 : BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
2479 1182843304 : ior |= r;
2480 1182843304 : tmp_elt.bits[ix] = r;
2481 : }
2482 :
2483 591421652 : if (ior)
2484 : {
2485 549087386 : changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
2486 : a_elt, &tmp_elt, changed);
2487 549087386 : new_element = true;
2488 549087386 : if (a_elt && a_elt->indx == b_elt->indx)
2489 479668953 : a_elt = a_elt->next;
2490 : }
2491 :
2492 591421652 : b_elt = b_elt->next;
2493 591421652 : kill_elt = kill_elt->next;
2494 : }
2495 : else
2496 : {
2497 495931632 : changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
2498 : a_elt, b_elt, changed);
2499 495931632 : new_element = true;
2500 :
2501 495931632 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2502 : {
2503 135336023 : a_elt = a_elt->next;
2504 135336023 : b_elt = b_elt->next;
2505 : }
2506 : else
2507 : {
2508 360595609 : if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
2509 49922225 : a_elt = a_elt->next;
2510 310673384 : else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
2511 310673384 : b_elt = b_elt->next;
2512 : }
2513 : }
2514 :
2515 1087353284 : if (new_element)
2516 : {
2517 1045019018 : dst_prev = *dst_prev_pnext;
2518 1045019018 : dst_prev_pnext = &dst_prev->next;
2519 1045019018 : dst_elt = *dst_prev_pnext;
2520 : }
2521 : }
2522 :
2523 467398126 : 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 467398126 : gcc_checking_assert (!dst->current == !dst->first);
2531 467398126 : if (dst->current)
2532 467398126 : dst->indx = dst->current->indx;
2533 :
2534 : return changed;
2535 : }
2536 :
2537 : /* A |= (B & ~C). Return true if A changes. */
2538 :
2539 : bool
2540 53062719 : bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c)
2541 : {
2542 53062719 : bitmap_element *a_elt = a->first;
2543 53062719 : const bitmap_element *b_elt = b->first;
2544 53062719 : const bitmap_element *c_elt = c->first;
2545 53062719 : bitmap_element and_elt;
2546 53062719 : bitmap_element *a_prev = NULL;
2547 53062719 : bitmap_element **a_prev_pnext = &a->first;
2548 53062719 : bool changed = false;
2549 53062719 : unsigned ix;
2550 :
2551 53062719 : gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
2552 :
2553 53062719 : if (a == b)
2554 : return false;
2555 52754788 : if (bitmap_empty_p (c))
2556 11383857 : return bitmap_ior_into (a, b);
2557 41370931 : else if (bitmap_empty_p (a))
2558 21129036 : return bitmap_and_compl (a, b, c);
2559 :
2560 20241895 : and_elt.indx = -1;
2561 67435119 : while (b_elt)
2562 : {
2563 : /* Advance C. */
2564 59415881 : while (c_elt && c_elt->indx < b_elt->indx)
2565 12222657 : c_elt = c_elt->next;
2566 :
2567 47193224 : const bitmap_element *and_elt_ptr;
2568 47193224 : if (c_elt && c_elt->indx == b_elt->indx)
2569 : {
2570 13377684 : BITMAP_WORD overall = 0;
2571 13377684 : and_elt_ptr = &and_elt;
2572 13377684 : and_elt.indx = b_elt->indx;
2573 40133052 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2574 : {
2575 26755368 : and_elt.bits[ix] = b_elt->bits[ix] & ~c_elt->bits[ix];
2576 26755368 : overall |= and_elt.bits[ix];
2577 : }
2578 13377684 : if (!overall)
2579 : {
2580 1256610 : b_elt = b_elt->next;
2581 1256610 : continue;
2582 : }
2583 : }
2584 : else
2585 : and_elt_ptr = b_elt;
2586 :
2587 45936614 : b_elt = b_elt->next;
2588 :
2589 : /* Now find a place to insert AND_ELT. */
2590 52797850 : do
2591 : {
2592 52797850 : ix = a_elt ? a_elt->indx : and_elt_ptr->indx;
2593 52797850 : if (ix == and_elt_ptr->indx)
2594 44716881 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt,
2595 : and_elt_ptr, changed);
2596 8080969 : else if (ix > and_elt_ptr->indx)
2597 1219733 : changed = bitmap_elt_copy (a, NULL, a_prev, and_elt_ptr, changed);
2598 :
2599 52797850 : a_prev = *a_prev_pnext;
2600 52797850 : a_prev_pnext = &a_prev->next;
2601 52797850 : a_elt = *a_prev_pnext;
2602 :
2603 : /* If A lagged behind B/C, we advanced it so loop once more. */
2604 : }
2605 52797850 : while (ix < and_elt_ptr->indx);
2606 : }
2607 :
2608 20241895 : gcc_checking_assert (!a->current == !a->first);
2609 20241895 : if (a->current)
2610 20241895 : a->indx = a->current->indx;
2611 : return changed;
2612 : }
2613 :
2614 : /* A |= (B & C). Return true if A changes. */
2615 :
2616 : bool
2617 11563164 : bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
2618 : {
2619 11563164 : bitmap_element *a_elt = a->first;
2620 11563164 : const bitmap_element *b_elt = b->first;
2621 11563164 : const bitmap_element *c_elt = c->first;
2622 11563164 : bitmap_element and_elt;
2623 11563164 : bitmap_element *a_prev = NULL;
2624 11563164 : bitmap_element **a_prev_pnext = &a->first;
2625 11563164 : bool changed = false;
2626 11563164 : unsigned ix;
2627 :
2628 11563164 : gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
2629 :
2630 11563164 : if (b == c)
2631 0 : return bitmap_ior_into (a, b);
2632 11563164 : if (bitmap_empty_p (b) || bitmap_empty_p (c))
2633 : return false;
2634 :
2635 : and_elt.indx = -1;
2636 26571310 : while (b_elt && c_elt)
2637 : {
2638 : BITMAP_WORD overall;
2639 :
2640 : /* Find a common item of B and C. */
2641 21563018 : while (b_elt->indx != c_elt->indx)
2642 : {
2643 6554870 : if (b_elt->indx < c_elt->indx)
2644 : {
2645 682837 : b_elt = b_elt->next;
2646 682837 : if (!b_elt)
2647 203140 : goto done;
2648 : }
2649 : else
2650 : {
2651 5872033 : c_elt = c_elt->next;
2652 5872033 : if (!c_elt)
2653 208812 : goto done;
2654 : }
2655 : }
2656 :
2657 15008148 : overall = 0;
2658 15008148 : and_elt.indx = b_elt->indx;
2659 45024444 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2660 : {
2661 30016296 : and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
2662 30016296 : overall |= and_elt.bits[ix];
2663 : }
2664 :
2665 15008148 : b_elt = b_elt->next;
2666 15008148 : c_elt = c_elt->next;
2667 15008148 : if (!overall)
2668 4497739 : continue;
2669 :
2670 : /* Now find a place to insert AND_ELT. */
2671 10510517 : do
2672 : {
2673 10510517 : ix = a_elt ? a_elt->indx : and_elt.indx;
2674 10510517 : if (ix == and_elt.indx)
2675 10459733 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
2676 50784 : else if (ix > and_elt.indx)
2677 50676 : changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
2678 :
2679 10510517 : a_prev = *a_prev_pnext;
2680 10510517 : a_prev_pnext = &a_prev->next;
2681 10510517 : a_elt = *a_prev_pnext;
2682 :
2683 : /* If A lagged behind B/C, we advanced it so loop once more. */
2684 : }
2685 10510517 : while (ix < and_elt.indx);
2686 : }
2687 :
2688 11151210 : done:
2689 11563162 : gcc_checking_assert (!a->current == !a->first);
2690 11563162 : if (a->current)
2691 8900844 : a->indx = a->current->indx;
2692 : return changed;
2693 : }
2694 :
2695 : /* Compute hash of bitmap (for purposes of hashing). */
2696 :
2697 : hashval_t
2698 260704750 : bitmap_hash (const_bitmap head)
2699 : {
2700 260704750 : const bitmap_element *ptr;
2701 260704750 : BITMAP_WORD hash = 0;
2702 260704750 : int ix;
2703 :
2704 260704750 : gcc_checking_assert (!head->tree_form);
2705 :
2706 595139669 : for (ptr = head->first; ptr; ptr = ptr->next)
2707 : {
2708 334434919 : hash ^= ptr->indx;
2709 1003304757 : for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
2710 668869838 : hash ^= ptr->bits[ix];
2711 : }
2712 260704750 : 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"
|
