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