]>
Commit | Line | Data |
---|---|---|
2f925a60 | 1 | /* Functions to support general ended bitmaps. |
d353bf18 | 2 | Copyright (C) 1997-2015 Free Software Foundation, Inc. |
2f925a60 | 3 | |
f12b58b3 | 4 | This file is part of GCC. |
2f925a60 | 5 | |
f12b58b3 | 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 | |
8c4c00c1 | 8 | Software Foundation; either version 3, or (at your option) any later |
f12b58b3 | 9 | version. |
2f925a60 | 10 | |
f12b58b3 | 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. | |
2f925a60 | 15 | |
16 | You should have received a copy of the GNU General Public License | |
8c4c00c1 | 17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
2f925a60 | 19 | |
2f925a60 | 20 | #include "config.h" |
405711de | 21 | #include "system.h" |
805e22b2 | 22 | #include "coretypes.h" |
2f925a60 | 23 | #include "obstack.h" |
1f3233d1 | 24 | #include "ggc.h" |
d6cb6164 | 25 | #include "bitmap.h" |
d9dd21a8 | 26 | #include "hash-table.h" |
bb4df124 | 27 | #include "vec.h" |
0ff42de5 | 28 | #include "inchash.h" |
29 | #include "mem-stats.h" | |
30 | #include "hash-map.h" | |
f65ffe0d | 31 | |
0ff42de5 | 32 | /* Memory allocation statistics purpose instance. */ |
33 | mem_alloc_description<bitmap_usage> bitmap_mem_desc; | |
f65ffe0d | 34 | |
35 | /* Register new bitmap. */ | |
36 | void | |
37 | bitmap_register (bitmap b MEM_STAT_DECL) | |
38 | { | |
0ff42de5 | 39 | bitmap_mem_desc.register_descriptor (b, BITMAP, false FINAL_PASS_MEM_STAT); |
f65ffe0d | 40 | } |
41 | ||
42 | /* Account the overhead. */ | |
43 | static void | |
44 | register_overhead (bitmap b, int amount) | |
45 | { | |
0ff42de5 | 46 | if (bitmap_mem_desc.contains_descriptor_for_instance (b)) |
47 | bitmap_mem_desc.register_instance_overhead (amount, b); | |
f65ffe0d | 48 | } |
2f925a60 | 49 | |
2f925a60 | 50 | /* Global data */ |
42fe97ed | 51 | bitmap_element bitmap_zero_bits; /* An element of all zero bits. */ |
52 | bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */ | |
fd6481cf | 53 | static int bitmap_default_obstack_depth; |
42fe97ed | 54 | static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of |
55 | GC'd elements. */ | |
2f925a60 | 56 | |
aecda0d6 | 57 | static void bitmap_elem_to_freelist (bitmap, bitmap_element *); |
58 | static void bitmap_element_free (bitmap, bitmap_element *); | |
59 | static bitmap_element *bitmap_element_allocate (bitmap); | |
056755a1 | 60 | static int bitmap_element_zerop (const bitmap_element *); |
aecda0d6 | 61 | static void bitmap_element_link (bitmap, bitmap_element *); |
5669bd62 | 62 | static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int); |
b6e72c17 | 63 | static void bitmap_elt_clear_from (bitmap, bitmap_element *); |
aecda0d6 | 64 | static bitmap_element *bitmap_find_bit (bitmap, unsigned int); |
2f925a60 | 65 | \f |
b6e72c17 | 66 | |
1f3233d1 | 67 | /* Add ELEM to the appropriate freelist. */ |
702216e3 | 68 | static inline void |
aecda0d6 | 69 | bitmap_elem_to_freelist (bitmap head, bitmap_element *elt) |
1f3233d1 | 70 | { |
42fe97ed | 71 | bitmap_obstack *bit_obstack = head->obstack; |
a0c938f0 | 72 | |
4bc590db | 73 | elt->next = NULL; |
42fe97ed | 74 | if (bit_obstack) |
1f3233d1 | 75 | { |
4bc590db | 76 | elt->prev = bit_obstack->elements; |
42fe97ed | 77 | bit_obstack->elements = elt; |
1f3233d1 | 78 | } |
79 | else | |
80 | { | |
4bc590db | 81 | elt->prev = bitmap_ggc_free; |
1f3233d1 | 82 | bitmap_ggc_free = elt; |
83 | } | |
84 | } | |
85 | ||
ca2968e9 | 86 | /* Free a bitmap element. Since these are allocated off the |
87 | bitmap_obstack, "free" actually means "put onto the freelist". */ | |
2f925a60 | 88 | |
702216e3 | 89 | static inline void |
aecda0d6 | 90 | bitmap_element_free (bitmap head, bitmap_element *elt) |
2f925a60 | 91 | { |
92 | bitmap_element *next = elt->next; | |
93 | bitmap_element *prev = elt->prev; | |
94 | ||
95 | if (prev) | |
96 | prev->next = next; | |
97 | ||
98 | if (next) | |
99 | next->prev = prev; | |
100 | ||
101 | if (head->first == elt) | |
102 | head->first = next; | |
103 | ||
104 | /* Since the first thing we try is to insert before current, | |
105 | make current the next entry in preference to the previous. */ | |
106 | if (head->current == elt) | |
8cbee12e | 107 | { |
108 | head->current = next != 0 ? next : prev; | |
109 | if (head->current) | |
110 | head->indx = head->current->indx; | |
a0c938f0 | 111 | else |
5669bd62 | 112 | head->indx = 0; |
8cbee12e | 113 | } |
ecd52ea9 | 114 | |
115 | if (GATHER_STATISTICS) | |
116 | register_overhead (head, -((int)sizeof (bitmap_element))); | |
117 | ||
1f3233d1 | 118 | bitmap_elem_to_freelist (head, elt); |
2f925a60 | 119 | } |
120 | \f | |
121 | /* Allocate a bitmap element. The bits are cleared, but nothing else is. */ | |
122 | ||
702216e3 | 123 | static inline bitmap_element * |
aecda0d6 | 124 | bitmap_element_allocate (bitmap head) |
2f925a60 | 125 | { |
126 | bitmap_element *element; | |
42fe97ed | 127 | bitmap_obstack *bit_obstack = head->obstack; |
a0c938f0 | 128 | |
42fe97ed | 129 | if (bit_obstack) |
23ec99a1 | 130 | { |
42fe97ed | 131 | element = bit_obstack->elements; |
a0c938f0 | 132 | |
42fe97ed | 133 | if (element) |
4bc590db | 134 | /* Use up the inner list first before looking at the next |
135 | element of the outer list. */ | |
136 | if (element->next) | |
137 | { | |
138 | bit_obstack->elements = element->next; | |
139 | bit_obstack->elements->prev = element->prev; | |
140 | } | |
141 | else | |
142 | /* Inner list was just a singleton. */ | |
143 | bit_obstack->elements = element->prev; | |
1f3233d1 | 144 | else |
42fe97ed | 145 | element = XOBNEW (&bit_obstack->obstack, bitmap_element); |
1f3233d1 | 146 | } |
147 | else | |
148 | { | |
42fe97ed | 149 | element = bitmap_ggc_free; |
150 | if (element) | |
4bc590db | 151 | /* Use up the inner list first before looking at the next |
152 | element of the outer list. */ | |
153 | if (element->next) | |
154 | { | |
155 | bitmap_ggc_free = element->next; | |
156 | bitmap_ggc_free->prev = element->prev; | |
157 | } | |
158 | else | |
159 | /* Inner list was just a singleton. */ | |
160 | bitmap_ggc_free = element->prev; | |
1f3233d1 | 161 | else |
25a27413 | 162 | element = ggc_alloc<bitmap_element> (); |
23ec99a1 | 163 | } |
2f925a60 | 164 | |
ecd52ea9 | 165 | if (GATHER_STATISTICS) |
166 | register_overhead (head, sizeof (bitmap_element)); | |
167 | ||
ca2968e9 | 168 | memset (element->bits, 0, sizeof (element->bits)); |
2f925a60 | 169 | |
170 | return element; | |
171 | } | |
172 | ||
42fe97ed | 173 | /* Remove ELT and all following elements from bitmap HEAD. */ |
114c7df6 | 174 | |
175 | void | |
42fe97ed | 176 | bitmap_elt_clear_from (bitmap head, bitmap_element *elt) |
177 | { | |
4bc590db | 178 | bitmap_element *prev; |
179 | bitmap_obstack *bit_obstack = head->obstack; | |
180 | ||
181 | if (!elt) return; | |
ecd52ea9 | 182 | |
183 | if (GATHER_STATISTICS) | |
184 | { | |
185 | int n = 0; | |
186 | for (prev = elt; prev; prev = prev->next) | |
187 | n++; | |
188 | register_overhead (head, -sizeof (bitmap_element) * n); | |
189 | } | |
42fe97ed | 190 | |
4bc590db | 191 | prev = elt->prev; |
192 | if (prev) | |
193 | { | |
194 | prev->next = NULL; | |
195 | if (head->current->indx > prev->indx) | |
196 | { | |
197 | head->current = prev; | |
198 | head->indx = prev->indx; | |
199 | } | |
a0c938f0 | 200 | } |
4bc590db | 201 | else |
202 | { | |
203 | head->first = NULL; | |
204 | head->current = NULL; | |
205 | head->indx = 0; | |
206 | } | |
207 | ||
a0c938f0 | 208 | /* Put the entire list onto the free list in one operation. */ |
4bc590db | 209 | if (bit_obstack) |
42fe97ed | 210 | { |
a0c938f0 | 211 | elt->prev = bit_obstack->elements; |
4bc590db | 212 | bit_obstack->elements = elt; |
213 | } | |
214 | else | |
215 | { | |
216 | elt->prev = bitmap_ggc_free; | |
217 | bitmap_ggc_free = elt; | |
42fe97ed | 218 | } |
219 | } | |
220 | ||
221 | /* Clear a bitmap by freeing the linked list. */ | |
222 | ||
c623bf22 | 223 | void |
42fe97ed | 224 | bitmap_clear (bitmap head) |
114c7df6 | 225 | { |
4bc590db | 226 | if (head->first) |
227 | bitmap_elt_clear_from (head, head->first); | |
42fe97ed | 228 | } |
229 | \f | |
230 | /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize | |
231 | the default bitmap obstack. */ | |
232 | ||
233 | void | |
234 | bitmap_obstack_initialize (bitmap_obstack *bit_obstack) | |
235 | { | |
236 | if (!bit_obstack) | |
fd6481cf | 237 | { |
238 | if (bitmap_default_obstack_depth++) | |
239 | return; | |
240 | bit_obstack = &bitmap_default_obstack; | |
241 | } | |
42fe97ed | 242 | |
243 | #if !defined(__GNUC__) || (__GNUC__ < 2) | |
244 | #define __alignof__(type) 0 | |
245 | #endif | |
246 | ||
247 | bit_obstack->elements = NULL; | |
248 | bit_obstack->heads = NULL; | |
249 | obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE, | |
250 | __alignof__ (bitmap_element), | |
251 | obstack_chunk_alloc, | |
252 | obstack_chunk_free); | |
114c7df6 | 253 | } |
254 | ||
42fe97ed | 255 | /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL, |
256 | release the default bitmap obstack. */ | |
257 | ||
258 | void | |
259 | bitmap_obstack_release (bitmap_obstack *bit_obstack) | |
260 | { | |
261 | if (!bit_obstack) | |
fd6481cf | 262 | { |
263 | if (--bitmap_default_obstack_depth) | |
264 | { | |
265 | gcc_assert (bitmap_default_obstack_depth > 0); | |
266 | return; | |
267 | } | |
268 | bit_obstack = &bitmap_default_obstack; | |
269 | } | |
a0c938f0 | 270 | |
42fe97ed | 271 | bit_obstack->elements = NULL; |
272 | bit_obstack->heads = NULL; | |
273 | obstack_free (&bit_obstack->obstack, NULL); | |
274 | } | |
275 | ||
276 | /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create | |
277 | it on the default bitmap obstack. */ | |
278 | ||
279 | bitmap | |
f65ffe0d | 280 | bitmap_obstack_alloc_stat (bitmap_obstack *bit_obstack MEM_STAT_DECL) |
42fe97ed | 281 | { |
282 | bitmap map; | |
283 | ||
284 | if (!bit_obstack) | |
285 | bit_obstack = &bitmap_default_obstack; | |
286 | map = bit_obstack->heads; | |
287 | if (map) | |
b3e7c666 | 288 | bit_obstack->heads = (struct bitmap_head *) map->first; |
42fe97ed | 289 | else |
290 | map = XOBNEW (&bit_obstack->obstack, bitmap_head); | |
f65ffe0d | 291 | bitmap_initialize_stat (map, bit_obstack PASS_MEM_STAT); |
ecd52ea9 | 292 | |
293 | if (GATHER_STATISTICS) | |
294 | register_overhead (map, sizeof (bitmap_head)); | |
42fe97ed | 295 | |
296 | return map; | |
297 | } | |
298 | ||
299 | /* Create a new GCd bitmap. */ | |
300 | ||
301 | bitmap | |
f65ffe0d | 302 | bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL) |
42fe97ed | 303 | { |
304 | bitmap map; | |
305 | ||
25a27413 | 306 | map = ggc_alloc<bitmap_head> (); |
f65ffe0d | 307 | bitmap_initialize_stat (map, NULL PASS_MEM_STAT); |
ecd52ea9 | 308 | |
309 | if (GATHER_STATISTICS) | |
310 | register_overhead (map, sizeof (bitmap_head)); | |
42fe97ed | 311 | |
312 | return map; | |
313 | } | |
314 | ||
42fe97ed | 315 | /* Release an obstack allocated bitmap. */ |
316 | ||
317 | void | |
318 | bitmap_obstack_free (bitmap map) | |
319 | { | |
0e06d11a | 320 | if (map) |
321 | { | |
322 | bitmap_clear (map); | |
76cd80c7 | 323 | map->first = (bitmap_element *) map->obstack->heads; |
ecd52ea9 | 324 | |
325 | if (GATHER_STATISTICS) | |
326 | register_overhead (map, -((int)sizeof (bitmap_head))); | |
327 | ||
0e06d11a | 328 | map->obstack->heads = map; |
329 | } | |
42fe97ed | 330 | } |
331 | ||
42fe97ed | 332 | \f |
2f925a60 | 333 | /* Return nonzero if all bits in an element are zero. */ |
334 | ||
702216e3 | 335 | static inline int |
056755a1 | 336 | bitmap_element_zerop (const bitmap_element *element) |
2f925a60 | 337 | { |
338 | #if BITMAP_ELEMENT_WORDS == 2 | |
339 | return (element->bits[0] | element->bits[1]) == 0; | |
340 | #else | |
84199e4b | 341 | unsigned i; |
2f925a60 | 342 | |
343 | for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
344 | if (element->bits[i] != 0) | |
345 | return 0; | |
346 | ||
347 | return 1; | |
348 | #endif | |
349 | } | |
350 | \f | |
351 | /* Link the bitmap element into the current bitmap linked list. */ | |
352 | ||
702216e3 | 353 | static inline void |
aecda0d6 | 354 | bitmap_element_link (bitmap head, bitmap_element *element) |
2f925a60 | 355 | { |
356 | unsigned int indx = element->indx; | |
357 | bitmap_element *ptr; | |
358 | ||
359 | /* If this is the first and only element, set it in. */ | |
360 | if (head->first == 0) | |
361 | { | |
362 | element->next = element->prev = 0; | |
363 | head->first = element; | |
364 | } | |
365 | ||
366 | /* If this index is less than that of the current element, it goes someplace | |
367 | before the current element. */ | |
368 | else if (indx < head->indx) | |
369 | { | |
370 | for (ptr = head->current; | |
371 | ptr->prev != 0 && ptr->prev->indx > indx; | |
372 | ptr = ptr->prev) | |
373 | ; | |
374 | ||
375 | if (ptr->prev) | |
376 | ptr->prev->next = element; | |
377 | else | |
378 | head->first = element; | |
379 | ||
380 | element->prev = ptr->prev; | |
381 | element->next = ptr; | |
382 | ptr->prev = element; | |
383 | } | |
384 | ||
385 | /* Otherwise, it must go someplace after the current element. */ | |
386 | else | |
387 | { | |
388 | for (ptr = head->current; | |
389 | ptr->next != 0 && ptr->next->indx < indx; | |
390 | ptr = ptr->next) | |
391 | ; | |
392 | ||
393 | if (ptr->next) | |
394 | ptr->next->prev = element; | |
395 | ||
396 | element->next = ptr->next; | |
397 | element->prev = ptr; | |
398 | ptr->next = element; | |
399 | } | |
400 | ||
401 | /* Set up so this is the first element searched. */ | |
402 | head->current = element; | |
403 | head->indx = indx; | |
404 | } | |
b6e72c17 | 405 | |
406 | /* Insert a new uninitialized element into bitmap HEAD after element | |
407 | ELT. If ELT is NULL, insert the element at the start. Return the | |
408 | new element. */ | |
409 | ||
410 | static bitmap_element * | |
5669bd62 | 411 | bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx) |
b6e72c17 | 412 | { |
413 | bitmap_element *node = bitmap_element_allocate (head); | |
5669bd62 | 414 | node->indx = indx; |
b6e72c17 | 415 | |
416 | if (!elt) | |
417 | { | |
418 | if (!head->current) | |
5669bd62 | 419 | { |
420 | head->current = node; | |
421 | head->indx = indx; | |
422 | } | |
b6e72c17 | 423 | node->next = head->first; |
424 | if (node->next) | |
425 | node->next->prev = node; | |
426 | head->first = node; | |
427 | node->prev = NULL; | |
428 | } | |
429 | else | |
430 | { | |
d16af188 | 431 | gcc_checking_assert (head->current); |
b6e72c17 | 432 | node->next = elt->next; |
433 | if (node->next) | |
434 | node->next->prev = node; | |
435 | elt->next = node; | |
436 | node->prev = elt; | |
437 | } | |
438 | return node; | |
439 | } | |
2f925a60 | 440 | \f |
ca2968e9 | 441 | /* Copy a bitmap to another bitmap. */ |
2f925a60 | 442 | |
443 | void | |
056755a1 | 444 | bitmap_copy (bitmap to, const_bitmap from) |
2f925a60 | 445 | { |
056755a1 | 446 | const bitmap_element *from_ptr; |
447 | bitmap_element *to_ptr = 0; | |
2f925a60 | 448 | |
449 | bitmap_clear (to); | |
450 | ||
2358393e | 451 | /* Copy elements in forward direction one at a time. */ |
2f925a60 | 452 | for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next) |
453 | { | |
1f3233d1 | 454 | bitmap_element *to_elt = bitmap_element_allocate (to); |
2f925a60 | 455 | |
456 | to_elt->indx = from_ptr->indx; | |
3c47d200 | 457 | memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits)); |
2f925a60 | 458 | |
459 | /* Here we have a special case of bitmap_element_link, for the case | |
460 | where we know the links are being entered in sequence. */ | |
461 | if (to_ptr == 0) | |
462 | { | |
463 | to->first = to->current = to_elt; | |
464 | to->indx = from_ptr->indx; | |
465 | to_elt->next = to_elt->prev = 0; | |
466 | } | |
467 | else | |
468 | { | |
469 | to_elt->prev = to_ptr; | |
470 | to_elt->next = 0; | |
471 | to_ptr->next = to_elt; | |
472 | } | |
473 | ||
474 | to_ptr = to_elt; | |
475 | } | |
476 | } | |
477 | \f | |
478 | /* Find a bitmap element that would hold a bitmap's bit. | |
479 | Update the `current' field even if we can't find an element that | |
480 | would hold the bitmap's bit to make eventual allocation | |
481 | faster. */ | |
482 | ||
702216e3 | 483 | static inline bitmap_element * |
aecda0d6 | 484 | bitmap_find_bit (bitmap head, unsigned int bit) |
2f925a60 | 485 | { |
486 | bitmap_element *element; | |
e5c8f082 | 487 | unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; |
2f925a60 | 488 | |
28d3effc | 489 | if (head->current == NULL |
9a3823f4 | 490 | || head->indx == indx) |
491 | return head->current; | |
28d3effc | 492 | if (head->current == head->first |
493 | && head->first->next == NULL) | |
494 | return NULL; | |
ecd52ea9 | 495 | |
0ff42de5 | 496 | /* Usage can be NULL due to allocated bitmaps for which we do not |
497 | call initialize function. */ | |
498 | bitmap_usage *usage = bitmap_mem_desc.get_descriptor_for_instance (head); | |
499 | ||
28d3effc | 500 | /* This bitmap has more than one element, and we're going to look |
501 | through the elements list. Count that as a search. */ | |
0ff42de5 | 502 | if (GATHER_STATISTICS && usage) |
503 | usage->m_nsearches++; | |
2f925a60 | 504 | |
4afe5544 | 505 | if (head->indx < indx) |
506 | /* INDX is beyond head->indx. Search from head->current | |
507 | forward. */ | |
508 | for (element = head->current; | |
509 | element->next != 0 && element->indx < indx; | |
510 | element = element->next) | |
ecd52ea9 | 511 | { |
0ff42de5 | 512 | if (GATHER_STATISTICS && usage) |
513 | usage->m_search_iter++; | |
ecd52ea9 | 514 | } |
4afe5544 | 515 | |
516 | else if (head->indx / 2 < indx) | |
517 | /* INDX is less than head->indx and closer to head->indx than to | |
518 | 0. Search from head->current backward. */ | |
2f925a60 | 519 | for (element = head->current; |
520 | element->prev != 0 && element->indx > indx; | |
521 | element = element->prev) | |
ecd52ea9 | 522 | { |
0ff42de5 | 523 | if (GATHER_STATISTICS && usage) |
524 | usage->m_search_iter++; | |
ecd52ea9 | 525 | } |
2f925a60 | 526 | |
527 | else | |
4afe5544 | 528 | /* INDX is less than head->indx and closer to 0 than to |
529 | head->indx. Search from head->first forward. */ | |
530 | for (element = head->first; | |
2f925a60 | 531 | element->next != 0 && element->indx < indx; |
532 | element = element->next) | |
0ff42de5 | 533 | if (GATHER_STATISTICS && usage) |
ecd52ea9 | 534 | { |
0ff42de5 | 535 | usage->m_search_iter++; |
ecd52ea9 | 536 | } |
2f925a60 | 537 | |
538 | /* `element' is the nearest to the one we want. If it's not the one we | |
539 | want, the one we want doesn't exist. */ | |
540 | head->current = element; | |
541 | head->indx = element->indx; | |
542 | if (element != 0 && element->indx != indx) | |
543 | element = 0; | |
544 | ||
545 | return element; | |
546 | } | |
547 | \f | |
b64035d2 | 548 | /* Clear a single bit in a bitmap. Return true if the bit changed. */ |
2f925a60 | 549 | |
b64035d2 | 550 | bool |
aecda0d6 | 551 | bitmap_clear_bit (bitmap head, int bit) |
2f925a60 | 552 | { |
056755a1 | 553 | bitmap_element *const ptr = bitmap_find_bit (head, bit); |
2f925a60 | 554 | |
555 | if (ptr != 0) | |
556 | { | |
e5c8f082 | 557 | unsigned bit_num = bit % BITMAP_WORD_BITS; |
558 | unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | |
b64035d2 | 559 | BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; |
560 | bool res = (ptr->bits[word_num] & bit_val) != 0; | |
561 | if (res) | |
a98d46f2 | 562 | { |
563 | ptr->bits[word_num] &= ~bit_val; | |
564 | /* If we cleared the entire word, free up the element. */ | |
565 | if (!ptr->bits[word_num] | |
566 | && bitmap_element_zerop (ptr)) | |
567 | bitmap_element_free (head, ptr); | |
568 | } | |
b64035d2 | 569 | |
570 | return res; | |
2f925a60 | 571 | } |
b64035d2 | 572 | |
573 | return false; | |
2f925a60 | 574 | } |
575 | ||
b64035d2 | 576 | /* Set a single bit in a bitmap. Return true if the bit changed. */ |
2f925a60 | 577 | |
b64035d2 | 578 | bool |
aecda0d6 | 579 | bitmap_set_bit (bitmap head, int bit) |
2f925a60 | 580 | { |
581 | bitmap_element *ptr = bitmap_find_bit (head, bit); | |
e5c8f082 | 582 | unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; |
583 | unsigned bit_num = bit % BITMAP_WORD_BITS; | |
584 | BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; | |
2f925a60 | 585 | |
586 | if (ptr == 0) | |
587 | { | |
1f3233d1 | 588 | ptr = bitmap_element_allocate (head); |
2f925a60 | 589 | ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; |
590 | ptr->bits[word_num] = bit_val; | |
591 | bitmap_element_link (head, ptr); | |
b64035d2 | 592 | return true; |
2f925a60 | 593 | } |
594 | else | |
b64035d2 | 595 | { |
596 | bool res = (ptr->bits[word_num] & bit_val) == 0; | |
597 | if (res) | |
598 | ptr->bits[word_num] |= bit_val; | |
599 | return res; | |
600 | } | |
2f925a60 | 601 | } |
ca2968e9 | 602 | |
2f925a60 | 603 | /* Return whether a bit is set within a bitmap. */ |
604 | ||
605 | int | |
aecda0d6 | 606 | bitmap_bit_p (bitmap head, int bit) |
2f925a60 | 607 | { |
608 | bitmap_element *ptr; | |
609 | unsigned bit_num; | |
610 | unsigned word_num; | |
611 | ||
612 | ptr = bitmap_find_bit (head, bit); | |
613 | if (ptr == 0) | |
614 | return 0; | |
615 | ||
e5c8f082 | 616 | bit_num = bit % BITMAP_WORD_BITS; |
617 | word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | |
2f925a60 | 618 | |
66b5ac3c | 619 | return (ptr->bits[word_num] >> bit_num) & 1; |
2f925a60 | 620 | } |
621 | \f | |
5669bd62 | 622 | #if GCC_VERSION < 3400 |
623 | /* Table of number of set bits in a character, indexed by value of char. */ | |
056755a1 | 624 | static const unsigned char popcount_table[] = |
5669bd62 | 625 | { |
626 | 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, | |
627 | 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, | |
628 | 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, | |
629 | 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, | |
630 | 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, | |
631 | 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, | |
632 | 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, | |
633 | 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, | |
634 | }; | |
635 | ||
636 | static unsigned long | |
637 | bitmap_popcount (BITMAP_WORD a) | |
638 | { | |
639 | unsigned long ret = 0; | |
640 | unsigned i; | |
641 | ||
642 | /* Just do this the table way for now */ | |
643 | for (i = 0; i < BITMAP_WORD_BITS; i+= 8) | |
644 | ret += popcount_table[(a >> i) & 0xff]; | |
645 | return ret; | |
646 | } | |
647 | #endif | |
648 | /* Count the number of bits set in the bitmap, and return it. */ | |
649 | ||
650 | unsigned long | |
056755a1 | 651 | bitmap_count_bits (const_bitmap a) |
5669bd62 | 652 | { |
653 | unsigned long count = 0; | |
056755a1 | 654 | const bitmap_element *elt; |
5669bd62 | 655 | unsigned ix; |
656 | ||
657 | for (elt = a->first; elt; elt = elt->next) | |
658 | { | |
659 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
660 | { | |
661 | #if GCC_VERSION >= 3400 | |
662 | /* Note that popcountl matches BITMAP_WORD in type, so the actual size | |
663 | of BITMAP_WORD is not material. */ | |
664 | count += __builtin_popcountl (elt->bits[ix]); | |
665 | #else | |
a0c938f0 | 666 | count += bitmap_popcount (elt->bits[ix]); |
5669bd62 | 667 | #endif |
668 | } | |
669 | } | |
670 | return count; | |
671 | } | |
a0c938f0 | 672 | |
6bd6739a | 673 | /* Return true if the bitmap has a single bit set. Otherwise return |
674 | false. */ | |
675 | ||
676 | bool | |
677 | bitmap_single_bit_set_p (const_bitmap a) | |
678 | { | |
679 | unsigned long count = 0; | |
680 | const bitmap_element *elt; | |
681 | unsigned ix; | |
682 | ||
683 | if (bitmap_empty_p (a)) | |
684 | return false; | |
685 | ||
686 | elt = a->first; | |
687 | /* As there are no completely empty bitmap elements, a second one | |
688 | means we have more than one bit set. */ | |
689 | if (elt->next != NULL) | |
690 | return false; | |
691 | ||
692 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
693 | { | |
694 | #if GCC_VERSION >= 3400 | |
695 | /* Note that popcountl matches BITMAP_WORD in type, so the actual size | |
696 | of BITMAP_WORD is not material. */ | |
697 | count += __builtin_popcountl (elt->bits[ix]); | |
698 | #else | |
699 | count += bitmap_popcount (elt->bits[ix]); | |
700 | #endif | |
701 | if (count > 1) | |
702 | return false; | |
703 | } | |
704 | ||
705 | return count == 1; | |
706 | } | |
5669bd62 | 707 | |
708 | ||
84199e4b | 709 | /* Return the bit number of the first set bit in the bitmap. The |
710 | bitmap must be non-empty. */ | |
114c7df6 | 711 | |
84199e4b | 712 | unsigned |
056755a1 | 713 | bitmap_first_set_bit (const_bitmap a) |
114c7df6 | 714 | { |
056755a1 | 715 | const bitmap_element *elt = a->first; |
84199e4b | 716 | unsigned bit_no; |
e5c8f082 | 717 | BITMAP_WORD word; |
84199e4b | 718 | unsigned ix; |
a0c938f0 | 719 | |
d16af188 | 720 | gcc_checking_assert (elt); |
84199e4b | 721 | bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; |
722 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
723 | { | |
724 | word = elt->bits[ix]; | |
725 | if (word) | |
726 | goto found_bit; | |
727 | } | |
64db345d | 728 | gcc_unreachable (); |
84199e4b | 729 | found_bit: |
730 | bit_no += ix * BITMAP_WORD_BITS; | |
114c7df6 | 731 | |
84199e4b | 732 | #if GCC_VERSION >= 3004 |
9af5ce0c | 733 | gcc_assert (sizeof (long) == sizeof (word)); |
84199e4b | 734 | bit_no += __builtin_ctzl (word); |
114c7df6 | 735 | #else |
84199e4b | 736 | /* Binary search for the first set bit. */ |
737 | #if BITMAP_WORD_BITS > 64 | |
738 | #error "Fill out the table." | |
114c7df6 | 739 | #endif |
84199e4b | 740 | #if BITMAP_WORD_BITS > 32 |
741 | if (!(word & 0xffffffff)) | |
742 | word >>= 32, bit_no += 32; | |
114c7df6 | 743 | #endif |
84199e4b | 744 | if (!(word & 0xffff)) |
745 | word >>= 16, bit_no += 16; | |
746 | if (!(word & 0xff)) | |
747 | word >>= 8, bit_no += 8; | |
748 | if (!(word & 0xf)) | |
749 | word >>= 4, bit_no += 4; | |
750 | if (!(word & 0x3)) | |
751 | word >>= 2, bit_no += 2; | |
752 | if (!(word & 0x1)) | |
753 | word >>= 1, bit_no += 1; | |
a0c938f0 | 754 | |
d16af188 | 755 | gcc_checking_assert (word & 1); |
114c7df6 | 756 | #endif |
84199e4b | 757 | return bit_no; |
114c7df6 | 758 | } |
ffa800d1 | 759 | |
760 | /* Return the bit number of the first set bit in the bitmap. The | |
761 | bitmap must be non-empty. */ | |
762 | ||
763 | unsigned | |
764 | bitmap_last_set_bit (const_bitmap a) | |
765 | { | |
766 | const bitmap_element *elt = a->current ? a->current : a->first; | |
767 | unsigned bit_no; | |
768 | BITMAP_WORD word; | |
769 | int ix; | |
770 | ||
d16af188 | 771 | gcc_checking_assert (elt); |
ffa800d1 | 772 | while (elt->next) |
773 | elt = elt->next; | |
774 | bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; | |
775 | for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--) | |
776 | { | |
777 | word = elt->bits[ix]; | |
778 | if (word) | |
779 | goto found_bit; | |
780 | } | |
781 | gcc_unreachable (); | |
782 | found_bit: | |
783 | bit_no += ix * BITMAP_WORD_BITS; | |
ffa800d1 | 784 | #if GCC_VERSION >= 3004 |
9af5ce0c | 785 | gcc_assert (sizeof (long) == sizeof (word)); |
7bf60644 | 786 | bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1; |
ffa800d1 | 787 | #else |
7bf60644 | 788 | /* Hopefully this is a twos-complement host... */ |
789 | BITMAP_WORD x = word; | |
790 | x |= (x >> 1); | |
791 | x |= (x >> 2); | |
792 | x |= (x >> 4); | |
793 | x |= (x >> 8); | |
794 | x |= (x >> 16); | |
ffa800d1 | 795 | #if BITMAP_WORD_BITS > 32 |
7bf60644 | 796 | x |= (x >> 32); |
ffa800d1 | 797 | #endif |
7bf60644 | 798 | bit_no += bitmap_popcount (x) - 1; |
ffa800d1 | 799 | #endif |
800 | ||
7bf60644 | 801 | return bit_no; |
ffa800d1 | 802 | } |
114c7df6 | 803 | \f |
2f925a60 | 804 | |
621a25ae | 805 | /* DST = A & B. */ |
b6e72c17 | 806 | |
807 | void | |
056755a1 | 808 | bitmap_and (bitmap dst, const_bitmap a, const_bitmap b) |
2f925a60 | 809 | { |
b6e72c17 | 810 | bitmap_element *dst_elt = dst->first; |
056755a1 | 811 | const bitmap_element *a_elt = a->first; |
812 | const bitmap_element *b_elt = b->first; | |
b6e72c17 | 813 | bitmap_element *dst_prev = NULL; |
66b5ac3c | 814 | |
07913396 | 815 | gcc_assert (dst != a && dst != b); |
816 | ||
817 | if (a == b) | |
818 | { | |
819 | bitmap_copy (dst, a); | |
820 | return; | |
821 | } | |
822 | ||
b6e72c17 | 823 | while (a_elt && b_elt) |
824 | { | |
825 | if (a_elt->indx < b_elt->indx) | |
826 | a_elt = a_elt->next; | |
827 | else if (b_elt->indx < a_elt->indx) | |
828 | b_elt = b_elt->next; | |
829 | else | |
830 | { | |
831 | /* Matching elts, generate A & B. */ | |
832 | unsigned ix; | |
833 | BITMAP_WORD ior = 0; | |
834 | ||
835 | if (!dst_elt) | |
5669bd62 | 836 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); |
a0c938f0 | 837 | else |
5669bd62 | 838 | dst_elt->indx = a_elt->indx; |
4399d500 | 839 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 840 | { |
841 | BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; | |
2f925a60 | 842 | |
b6e72c17 | 843 | dst_elt->bits[ix] = r; |
844 | ior |= r; | |
845 | } | |
846 | if (ior) | |
847 | { | |
848 | dst_prev = dst_elt; | |
849 | dst_elt = dst_elt->next; | |
850 | } | |
851 | a_elt = a_elt->next; | |
852 | b_elt = b_elt->next; | |
853 | } | |
854 | } | |
c926c35f | 855 | /* Ensure that dst->current is valid. */ |
856 | dst->current = dst->first; | |
b6e72c17 | 857 | bitmap_elt_clear_from (dst, dst_elt); |
0ea2d350 | 858 | gcc_checking_assert (!dst->current == !dst->first); |
b6e72c17 | 859 | if (dst->current) |
860 | dst->indx = dst->current->indx; | |
861 | } | |
862 | ||
ea9538fb | 863 | /* A &= B. Return true if A changed. */ |
b6e72c17 | 864 | |
ea9538fb | 865 | bool |
056755a1 | 866 | bitmap_and_into (bitmap a, const_bitmap b) |
b6e72c17 | 867 | { |
868 | bitmap_element *a_elt = a->first; | |
056755a1 | 869 | const bitmap_element *b_elt = b->first; |
b6e72c17 | 870 | bitmap_element *next; |
ea9538fb | 871 | bool changed = false; |
2f925a60 | 872 | |
a0c938f0 | 873 | if (a == b) |
ea9538fb | 874 | return false; |
07913396 | 875 | |
b6e72c17 | 876 | while (a_elt && b_elt) |
2f925a60 | 877 | { |
b6e72c17 | 878 | if (a_elt->indx < b_elt->indx) |
879 | { | |
880 | next = a_elt->next; | |
881 | bitmap_element_free (a, a_elt); | |
882 | a_elt = next; | |
ea9538fb | 883 | changed = true; |
b6e72c17 | 884 | } |
885 | else if (b_elt->indx < a_elt->indx) | |
886 | b_elt = b_elt->next; | |
887 | else | |
2f925a60 | 888 | { |
b6e72c17 | 889 | /* Matching elts, generate A &= B. */ |
890 | unsigned ix; | |
891 | BITMAP_WORD ior = 0; | |
892 | ||
4399d500 | 893 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 894 | { |
895 | BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; | |
ea9538fb | 896 | if (a_elt->bits[ix] != r) |
897 | changed = true; | |
b6e72c17 | 898 | a_elt->bits[ix] = r; |
899 | ior |= r; | |
900 | } | |
901 | next = a_elt->next; | |
902 | if (!ior) | |
903 | bitmap_element_free (a, a_elt); | |
904 | a_elt = next; | |
905 | b_elt = b_elt->next; | |
2f925a60 | 906 | } |
b6e72c17 | 907 | } |
ea9538fb | 908 | |
909 | if (a_elt) | |
910 | { | |
911 | changed = true; | |
912 | bitmap_elt_clear_from (a, a_elt); | |
913 | } | |
914 | ||
0ea2d350 | 915 | gcc_checking_assert (!a->current == !a->first |
916 | && (!a->current || a->indx == a->current->indx)); | |
ea9538fb | 917 | |
918 | return changed; | |
b6e72c17 | 919 | } |
920 | ||
3072d30e | 921 | |
922 | /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT | |
923 | if non-NULL. CHANGED is true if the destination bitmap had already been | |
924 | changed; the new value of CHANGED is returned. */ | |
925 | ||
926 | static inline bool | |
927 | bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, | |
056755a1 | 928 | const bitmap_element *src_elt, bool changed) |
3072d30e | 929 | { |
930 | if (!changed && dst_elt && dst_elt->indx == src_elt->indx) | |
931 | { | |
932 | unsigned ix; | |
933 | ||
4399d500 | 934 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 935 | if (src_elt->bits[ix] != dst_elt->bits[ix]) |
936 | { | |
937 | dst_elt->bits[ix] = src_elt->bits[ix]; | |
938 | changed = true; | |
939 | } | |
940 | } | |
941 | else | |
942 | { | |
943 | changed = true; | |
944 | if (!dst_elt) | |
945 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx); | |
946 | else | |
947 | dst_elt->indx = src_elt->indx; | |
948 | memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits)); | |
949 | } | |
950 | return changed; | |
951 | } | |
952 | ||
953 | ||
954 | ||
b6e72c17 | 955 | /* DST = A & ~B */ |
956 | ||
3072d30e | 957 | bool |
056755a1 | 958 | bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b) |
b6e72c17 | 959 | { |
960 | bitmap_element *dst_elt = dst->first; | |
056755a1 | 961 | const bitmap_element *a_elt = a->first; |
962 | const bitmap_element *b_elt = b->first; | |
b6e72c17 | 963 | bitmap_element *dst_prev = NULL; |
3072d30e | 964 | bitmap_element **dst_prev_pnext = &dst->first; |
965 | bool changed = false; | |
b6e72c17 | 966 | |
07913396 | 967 | gcc_assert (dst != a && dst != b); |
a0c938f0 | 968 | |
07913396 | 969 | if (a == b) |
970 | { | |
3072d30e | 971 | changed = !bitmap_empty_p (dst); |
07913396 | 972 | bitmap_clear (dst); |
3072d30e | 973 | return changed; |
07913396 | 974 | } |
975 | ||
b6e72c17 | 976 | while (a_elt) |
977 | { | |
3072d30e | 978 | while (b_elt && b_elt->indx < a_elt->indx) |
979 | b_elt = b_elt->next; | |
980 | ||
981 | if (!b_elt || b_elt->indx > a_elt->indx) | |
2f925a60 | 982 | { |
3072d30e | 983 | changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed); |
984 | dst_prev = *dst_prev_pnext; | |
985 | dst_prev_pnext = &dst_prev->next; | |
986 | dst_elt = *dst_prev_pnext; | |
b6e72c17 | 987 | a_elt = a_elt->next; |
2f925a60 | 988 | } |
3072d30e | 989 | |
2f925a60 | 990 | else |
991 | { | |
b6e72c17 | 992 | /* Matching elts, generate A & ~B. */ |
993 | unsigned ix; | |
994 | BITMAP_WORD ior = 0; | |
995 | ||
3072d30e | 996 | if (!changed && dst_elt && dst_elt->indx == a_elt->indx) |
997 | { | |
4399d500 | 998 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 999 | { |
1000 | BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; | |
1001 | ||
1002 | if (dst_elt->bits[ix] != r) | |
1003 | { | |
1004 | changed = true; | |
1005 | dst_elt->bits[ix] = r; | |
1006 | } | |
1007 | ior |= r; | |
1008 | } | |
1009 | } | |
a0c938f0 | 1010 | else |
b6e72c17 | 1011 | { |
3072d30e | 1012 | bool new_element; |
1013 | if (!dst_elt || dst_elt->indx > a_elt->indx) | |
1014 | { | |
1015 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | |
1016 | new_element = true; | |
1017 | } | |
1018 | else | |
1019 | { | |
1020 | dst_elt->indx = a_elt->indx; | |
1021 | new_element = false; | |
1022 | } | |
b6e72c17 | 1023 | |
4399d500 | 1024 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 1025 | { |
1026 | BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; | |
1027 | ||
1028 | dst_elt->bits[ix] = r; | |
1029 | ior |= r; | |
1030 | } | |
1031 | ||
1032 | if (ior) | |
1033 | changed = true; | |
1034 | else | |
1035 | { | |
1036 | changed |= !new_element; | |
1037 | bitmap_element_free (dst, dst_elt); | |
1038 | dst_elt = *dst_prev_pnext; | |
1039 | } | |
b6e72c17 | 1040 | } |
3072d30e | 1041 | |
b6e72c17 | 1042 | if (ior) |
1043 | { | |
3072d30e | 1044 | dst_prev = *dst_prev_pnext; |
1045 | dst_prev_pnext = &dst_prev->next; | |
1046 | dst_elt = *dst_prev_pnext; | |
b6e72c17 | 1047 | } |
1048 | a_elt = a_elt->next; | |
1049 | b_elt = b_elt->next; | |
2f925a60 | 1050 | } |
b6e72c17 | 1051 | } |
3072d30e | 1052 | |
c926c35f | 1053 | /* Ensure that dst->current is valid. */ |
1054 | dst->current = dst->first; | |
3072d30e | 1055 | |
1056 | if (dst_elt) | |
1057 | { | |
1058 | changed = true; | |
1059 | bitmap_elt_clear_from (dst, dst_elt); | |
1060 | } | |
0ea2d350 | 1061 | gcc_checking_assert (!dst->current == !dst->first); |
b6e72c17 | 1062 | if (dst->current) |
1063 | dst->indx = dst->current->indx; | |
3072d30e | 1064 | |
1065 | return changed; | |
b6e72c17 | 1066 | } |
1067 | ||
0db4e233 | 1068 | /* A &= ~B. Returns true if A changes */ |
2f925a60 | 1069 | |
0db4e233 | 1070 | bool |
056755a1 | 1071 | bitmap_and_compl_into (bitmap a, const_bitmap b) |
b6e72c17 | 1072 | { |
1073 | bitmap_element *a_elt = a->first; | |
056755a1 | 1074 | const bitmap_element *b_elt = b->first; |
b6e72c17 | 1075 | bitmap_element *next; |
0db4e233 | 1076 | BITMAP_WORD changed = 0; |
b6e72c17 | 1077 | |
07913396 | 1078 | if (a == b) |
1079 | { | |
1080 | if (bitmap_empty_p (a)) | |
1081 | return false; | |
1082 | else | |
1083 | { | |
1084 | bitmap_clear (a); | |
1085 | return true; | |
1086 | } | |
1087 | } | |
1088 | ||
b6e72c17 | 1089 | while (a_elt && b_elt) |
1090 | { | |
1091 | if (a_elt->indx < b_elt->indx) | |
1092 | a_elt = a_elt->next; | |
1093 | else if (b_elt->indx < a_elt->indx) | |
1094 | b_elt = b_elt->next; | |
1095 | else | |
66b5ac3c | 1096 | { |
b6e72c17 | 1097 | /* Matching elts, generate A &= ~B. */ |
1098 | unsigned ix; | |
1099 | BITMAP_WORD ior = 0; | |
1100 | ||
4399d500 | 1101 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 1102 | { |
0db4e233 | 1103 | BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; |
1104 | BITMAP_WORD r = a_elt->bits[ix] ^ cleared; | |
b6e72c17 | 1105 | |
1106 | a_elt->bits[ix] = r; | |
0db4e233 | 1107 | changed |= cleared; |
b6e72c17 | 1108 | ior |= r; |
1109 | } | |
1110 | next = a_elt->next; | |
1111 | if (!ior) | |
1112 | bitmap_element_free (a, a_elt); | |
1113 | a_elt = next; | |
1114 | b_elt = b_elt->next; | |
66b5ac3c | 1115 | } |
b6e72c17 | 1116 | } |
0ea2d350 | 1117 | gcc_checking_assert (!a->current == !a->first |
1118 | && (!a->current || a->indx == a->current->indx)); | |
0db4e233 | 1119 | return changed != 0; |
b6e72c17 | 1120 | } |
1121 | ||
3072d30e | 1122 | /* Set COUNT bits from START in HEAD. */ |
1123 | void | |
1124 | bitmap_set_range (bitmap head, unsigned int start, unsigned int count) | |
1125 | { | |
1126 | unsigned int first_index, end_bit_plus1, last_index; | |
1127 | bitmap_element *elt, *elt_prev; | |
1128 | unsigned int i; | |
1129 | ||
1130 | if (!count) | |
1131 | return; | |
1132 | ||
837d3ea8 | 1133 | if (count == 1) |
1134 | { | |
1135 | bitmap_set_bit (head, start); | |
1136 | return; | |
1137 | } | |
1138 | ||
3072d30e | 1139 | first_index = start / BITMAP_ELEMENT_ALL_BITS; |
1140 | end_bit_plus1 = start + count; | |
1141 | last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; | |
1142 | elt = bitmap_find_bit (head, start); | |
1143 | ||
1144 | /* If bitmap_find_bit returns zero, the current is the closest block | |
1145 | to the result. Otherwise, just use bitmap_element_allocate to | |
1146 | ensure ELT is set; in the loop below, ELT == NULL means "insert | |
1147 | at the end of the bitmap". */ | |
1148 | if (!elt) | |
1149 | { | |
1150 | elt = bitmap_element_allocate (head); | |
1151 | elt->indx = first_index; | |
1152 | bitmap_element_link (head, elt); | |
1153 | } | |
1154 | ||
d16af188 | 1155 | gcc_checking_assert (elt->indx == first_index); |
3072d30e | 1156 | elt_prev = elt->prev; |
1157 | for (i = first_index; i <= last_index; i++) | |
1158 | { | |
1159 | unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS; | |
1160 | unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; | |
1161 | ||
1162 | unsigned int first_word_to_mod; | |
1163 | BITMAP_WORD first_mask; | |
1164 | unsigned int last_word_to_mod; | |
1165 | BITMAP_WORD last_mask; | |
1166 | unsigned int ix; | |
1167 | ||
1168 | if (!elt || elt->indx != i) | |
1169 | elt = bitmap_elt_insert_after (head, elt_prev, i); | |
1170 | ||
1171 | if (elt_start_bit <= start) | |
1172 | { | |
1173 | /* The first bit to turn on is somewhere inside this | |
1174 | elt. */ | |
1175 | first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; | |
1176 | ||
1177 | /* This mask should have 1s in all bits >= start position. */ | |
1178 | first_mask = | |
1179 | (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; | |
1180 | first_mask = ~first_mask; | |
1181 | } | |
1182 | else | |
1183 | { | |
1184 | /* The first bit to turn on is below this start of this elt. */ | |
1185 | first_word_to_mod = 0; | |
1186 | first_mask = ~(BITMAP_WORD) 0; | |
1187 | } | |
1188 | ||
1189 | if (elt_end_bit_plus1 <= end_bit_plus1) | |
1190 | { | |
1191 | /* The last bit to turn on is beyond this elt. */ | |
1192 | last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; | |
1193 | last_mask = ~(BITMAP_WORD) 0; | |
1194 | } | |
1195 | else | |
1196 | { | |
1197 | /* The last bit to turn on is inside to this elt. */ | |
1198 | last_word_to_mod = | |
1199 | (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; | |
1200 | ||
1201 | /* The last mask should have 1s below the end bit. */ | |
1202 | last_mask = | |
1203 | (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1; | |
1204 | } | |
1205 | ||
1206 | if (first_word_to_mod == last_word_to_mod) | |
1207 | { | |
1208 | BITMAP_WORD mask = first_mask & last_mask; | |
1209 | elt->bits[first_word_to_mod] |= mask; | |
1210 | } | |
1211 | else | |
1212 | { | |
1213 | elt->bits[first_word_to_mod] |= first_mask; | |
1214 | if (BITMAP_ELEMENT_WORDS > 2) | |
1215 | for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++) | |
1216 | elt->bits[ix] = ~(BITMAP_WORD) 0; | |
1217 | elt->bits[last_word_to_mod] |= last_mask; | |
1218 | } | |
1219 | ||
1220 | elt_prev = elt; | |
1221 | elt = elt->next; | |
1222 | } | |
1223 | ||
1224 | head->current = elt ? elt : elt_prev; | |
1225 | head->indx = head->current->indx; | |
1226 | } | |
1227 | ||
5669bd62 | 1228 | /* Clear COUNT bits from START in HEAD. */ |
1229 | void | |
1230 | bitmap_clear_range (bitmap head, unsigned int start, unsigned int count) | |
1231 | { | |
3072d30e | 1232 | unsigned int first_index, end_bit_plus1, last_index; |
1233 | bitmap_element *elt; | |
1234 | ||
1235 | if (!count) | |
1236 | return; | |
1237 | ||
837d3ea8 | 1238 | if (count == 1) |
1239 | { | |
1240 | bitmap_clear_bit (head, start); | |
1241 | return; | |
1242 | } | |
1243 | ||
3072d30e | 1244 | first_index = start / BITMAP_ELEMENT_ALL_BITS; |
1245 | end_bit_plus1 = start + count; | |
1246 | last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; | |
1247 | elt = bitmap_find_bit (head, start); | |
5669bd62 | 1248 | |
1249 | /* If bitmap_find_bit returns zero, the current is the closest block | |
1250 | to the result. If the current is less than first index, find the | |
1251 | next one. Otherwise, just set elt to be current. */ | |
1252 | if (!elt) | |
a0c938f0 | 1253 | { |
5669bd62 | 1254 | if (head->current) |
1255 | { | |
1256 | if (head->indx < first_index) | |
1257 | { | |
1258 | elt = head->current->next; | |
1259 | if (!elt) | |
1260 | return; | |
1261 | } | |
a0c938f0 | 1262 | else |
5669bd62 | 1263 | elt = head->current; |
1264 | } | |
1265 | else | |
1266 | return; | |
1267 | } | |
1268 | ||
1269 | while (elt && (elt->indx <= last_index)) | |
1270 | { | |
1271 | bitmap_element * next_elt = elt->next; | |
1272 | unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS; | |
1273 | unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; | |
1274 | ||
1275 | ||
1276 | if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1) | |
1277 | /* Get rid of the entire elt and go to the next one. */ | |
1278 | bitmap_element_free (head, elt); | |
a0c938f0 | 1279 | else |
5669bd62 | 1280 | { |
1281 | /* Going to have to knock out some bits in this elt. */ | |
a0c938f0 | 1282 | unsigned int first_word_to_mod; |
1283 | BITMAP_WORD first_mask; | |
5669bd62 | 1284 | unsigned int last_word_to_mod; |
1285 | BITMAP_WORD last_mask; | |
1286 | unsigned int i; | |
1287 | bool clear = true; | |
1288 | ||
1289 | if (elt_start_bit <= start) | |
1290 | { | |
1291 | /* The first bit to turn off is somewhere inside this | |
1292 | elt. */ | |
1293 | first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; | |
1294 | ||
1295 | /* This mask should have 1s in all bits >= start position. */ | |
a0c938f0 | 1296 | first_mask = |
5669bd62 | 1297 | (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; |
1298 | first_mask = ~first_mask; | |
1299 | } | |
1300 | else | |
1301 | { | |
1302 | /* The first bit to turn off is below this start of this elt. */ | |
1303 | first_word_to_mod = 0; | |
1304 | first_mask = 0; | |
1305 | first_mask = ~first_mask; | |
a0c938f0 | 1306 | } |
1307 | ||
5669bd62 | 1308 | if (elt_end_bit_plus1 <= end_bit_plus1) |
1309 | { | |
1310 | /* The last bit to turn off is beyond this elt. */ | |
1311 | last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; | |
1312 | last_mask = 0; | |
1313 | last_mask = ~last_mask; | |
1314 | } | |
1315 | else | |
1316 | { | |
1317 | /* The last bit to turn off is inside to this elt. */ | |
a0c938f0 | 1318 | last_word_to_mod = |
5669bd62 | 1319 | (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; |
1320 | ||
1321 | /* The last mask should have 1s below the end bit. */ | |
a0c938f0 | 1322 | last_mask = |
5669bd62 | 1323 | (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1; |
1324 | } | |
1325 | ||
1326 | ||
1327 | if (first_word_to_mod == last_word_to_mod) | |
1328 | { | |
1329 | BITMAP_WORD mask = first_mask & last_mask; | |
1330 | elt->bits[first_word_to_mod] &= ~mask; | |
1331 | } | |
1332 | else | |
1333 | { | |
1334 | elt->bits[first_word_to_mod] &= ~first_mask; | |
3072d30e | 1335 | if (BITMAP_ELEMENT_WORDS > 2) |
1336 | for (i = first_word_to_mod + 1; i < last_word_to_mod; i++) | |
1337 | elt->bits[i] = 0; | |
5669bd62 | 1338 | elt->bits[last_word_to_mod] &= ~last_mask; |
1339 | } | |
1340 | for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
1341 | if (elt->bits[i]) | |
1342 | { | |
1343 | clear = false; | |
1344 | break; | |
1345 | } | |
1346 | /* Check to see if there are any bits left. */ | |
1347 | if (clear) | |
1348 | bitmap_element_free (head, elt); | |
1349 | } | |
1350 | elt = next_elt; | |
1351 | } | |
a0c938f0 | 1352 | |
5669bd62 | 1353 | if (elt) |
1354 | { | |
1355 | head->current = elt; | |
1356 | head->indx = head->current->indx; | |
1357 | } | |
1358 | } | |
1359 | ||
1360 | /* A = ~A & B. */ | |
1361 | ||
1362 | void | |
056755a1 | 1363 | bitmap_compl_and_into (bitmap a, const_bitmap b) |
5669bd62 | 1364 | { |
1365 | bitmap_element *a_elt = a->first; | |
056755a1 | 1366 | const bitmap_element *b_elt = b->first; |
5669bd62 | 1367 | bitmap_element *a_prev = NULL; |
1368 | bitmap_element *next; | |
1369 | ||
1370 | gcc_assert (a != b); | |
1371 | ||
1372 | if (bitmap_empty_p (a)) | |
1373 | { | |
1374 | bitmap_copy (a, b); | |
1375 | return; | |
1376 | } | |
1377 | if (bitmap_empty_p (b)) | |
1378 | { | |
1379 | bitmap_clear (a); | |
1380 | return; | |
1381 | } | |
1382 | ||
1383 | while (a_elt || b_elt) | |
1384 | { | |
1385 | if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
1386 | { | |
1387 | /* A is before B. Remove A */ | |
1388 | next = a_elt->next; | |
1389 | a_prev = a_elt->prev; | |
1390 | bitmap_element_free (a, a_elt); | |
1391 | a_elt = next; | |
1392 | } | |
1393 | else if (!a_elt || b_elt->indx < a_elt->indx) | |
1394 | { | |
1395 | /* B is before A. Copy B. */ | |
1396 | next = bitmap_elt_insert_after (a, a_prev, b_elt->indx); | |
1397 | memcpy (next->bits, b_elt->bits, sizeof (next->bits)); | |
1398 | a_prev = next; | |
1399 | b_elt = b_elt->next; | |
1400 | } | |
1401 | else | |
1402 | { | |
1403 | /* Matching elts, generate A = ~A & B. */ | |
1404 | unsigned ix; | |
1405 | BITMAP_WORD ior = 0; | |
1406 | ||
4399d500 | 1407 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
5669bd62 | 1408 | { |
1409 | BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; | |
1410 | BITMAP_WORD r = b_elt->bits[ix] ^ cleared; | |
1411 | ||
1412 | a_elt->bits[ix] = r; | |
1413 | ior |= r; | |
1414 | } | |
1415 | next = a_elt->next; | |
1416 | if (!ior) | |
1417 | bitmap_element_free (a, a_elt); | |
1418 | else | |
1419 | a_prev = a_elt; | |
1420 | a_elt = next; | |
1421 | b_elt = b_elt->next; | |
1422 | } | |
1423 | } | |
0ea2d350 | 1424 | gcc_checking_assert (!a->current == !a->first |
1425 | && (!a->current || a->indx == a->current->indx)); | |
5669bd62 | 1426 | return; |
1427 | } | |
1428 | ||
3072d30e | 1429 | |
1430 | /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV, | |
1431 | overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap | |
1432 | had already been changed; the new value of CHANGED is returned. */ | |
1433 | ||
1434 | static inline bool | |
1435 | bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, | |
056755a1 | 1436 | const bitmap_element *a_elt, const bitmap_element *b_elt, |
3072d30e | 1437 | bool changed) |
1438 | { | |
1439 | gcc_assert (a_elt || b_elt); | |
1440 | ||
1441 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) | |
1442 | { | |
1443 | /* Matching elts, generate A | B. */ | |
1444 | unsigned ix; | |
1445 | ||
1446 | if (!changed && dst_elt && dst_elt->indx == a_elt->indx) | |
1447 | { | |
4399d500 | 1448 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 1449 | { |
1450 | BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; | |
1451 | if (r != dst_elt->bits[ix]) | |
1452 | { | |
1453 | dst_elt->bits[ix] = r; | |
1454 | changed = true; | |
1455 | } | |
1456 | } | |
1457 | } | |
1458 | else | |
1459 | { | |
1460 | changed = true; | |
1461 | if (!dst_elt) | |
1462 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | |
1463 | else | |
1464 | dst_elt->indx = a_elt->indx; | |
4399d500 | 1465 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 1466 | { |
1467 | BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; | |
1468 | dst_elt->bits[ix] = r; | |
1469 | } | |
1470 | } | |
1471 | } | |
1472 | else | |
1473 | { | |
1474 | /* Copy a single element. */ | |
056755a1 | 1475 | const bitmap_element *src; |
3072d30e | 1476 | |
1477 | if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
1478 | src = a_elt; | |
1479 | else | |
1480 | src = b_elt; | |
1481 | ||
d16af188 | 1482 | gcc_checking_assert (src); |
3072d30e | 1483 | changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed); |
1484 | } | |
1485 | return changed; | |
1486 | } | |
1487 | ||
1488 | ||
b6e72c17 | 1489 | /* DST = A | B. Return true if DST changes. */ |
1490 | ||
1491 | bool | |
056755a1 | 1492 | bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b) |
b6e72c17 | 1493 | { |
1494 | bitmap_element *dst_elt = dst->first; | |
056755a1 | 1495 | const bitmap_element *a_elt = a->first; |
1496 | const bitmap_element *b_elt = b->first; | |
b6e72c17 | 1497 | bitmap_element *dst_prev = NULL; |
3072d30e | 1498 | bitmap_element **dst_prev_pnext = &dst->first; |
a0c938f0 | 1499 | bool changed = false; |
b6e72c17 | 1500 | |
07913396 | 1501 | gcc_assert (dst != a && dst != b); |
1502 | ||
b6e72c17 | 1503 | while (a_elt || b_elt) |
1504 | { | |
3072d30e | 1505 | changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed); |
1506 | ||
b6e72c17 | 1507 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) |
66b5ac3c | 1508 | { |
b6e72c17 | 1509 | a_elt = a_elt->next; |
1510 | b_elt = b_elt->next; | |
66b5ac3c | 1511 | } |
1512 | else | |
2f925a60 | 1513 | { |
3072d30e | 1514 | if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) |
1515 | a_elt = a_elt->next; | |
1516 | else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) | |
1517 | b_elt = b_elt->next; | |
2f925a60 | 1518 | } |
3072d30e | 1519 | |
1520 | dst_prev = *dst_prev_pnext; | |
1521 | dst_prev_pnext = &dst_prev->next; | |
1522 | dst_elt = *dst_prev_pnext; | |
b6e72c17 | 1523 | } |
1524 | ||
1525 | if (dst_elt) | |
1526 | { | |
1527 | changed = true; | |
85ac1c40 | 1528 | /* Ensure that dst->current is valid. */ |
1529 | dst->current = dst->first; | |
b6e72c17 | 1530 | bitmap_elt_clear_from (dst, dst_elt); |
1531 | } | |
0ea2d350 | 1532 | gcc_checking_assert (!dst->current == !dst->first); |
b6e72c17 | 1533 | if (dst->current) |
1534 | dst->indx = dst->current->indx; | |
1535 | return changed; | |
1536 | } | |
2f925a60 | 1537 | |
b6e72c17 | 1538 | /* A |= B. Return true if A changes. */ |
1539 | ||
1540 | bool | |
056755a1 | 1541 | bitmap_ior_into (bitmap a, const_bitmap b) |
b6e72c17 | 1542 | { |
1543 | bitmap_element *a_elt = a->first; | |
056755a1 | 1544 | const bitmap_element *b_elt = b->first; |
b6e72c17 | 1545 | bitmap_element *a_prev = NULL; |
3072d30e | 1546 | bitmap_element **a_prev_pnext = &a->first; |
b6e72c17 | 1547 | bool changed = false; |
1548 | ||
07913396 | 1549 | if (a == b) |
1550 | return false; | |
1551 | ||
b6e72c17 | 1552 | while (b_elt) |
1553 | { | |
3072d30e | 1554 | /* If A lags behind B, just advance it. */ |
1555 | if (!a_elt || a_elt->indx == b_elt->indx) | |
b6e72c17 | 1556 | { |
3072d30e | 1557 | changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed); |
b6e72c17 | 1558 | b_elt = b_elt->next; |
d587687f | 1559 | } |
3072d30e | 1560 | else if (a_elt->indx > b_elt->indx) |
d587687f | 1561 | { |
3072d30e | 1562 | changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed); |
b6e72c17 | 1563 | b_elt = b_elt->next; |
2f925a60 | 1564 | } |
3072d30e | 1565 | |
1566 | a_prev = *a_prev_pnext; | |
1567 | a_prev_pnext = &a_prev->next; | |
1568 | a_elt = *a_prev_pnext; | |
2f925a60 | 1569 | } |
3072d30e | 1570 | |
0ea2d350 | 1571 | gcc_checking_assert (!a->current == !a->first); |
b6e72c17 | 1572 | if (a->current) |
1573 | a->indx = a->current->indx; | |
1574 | return changed; | |
1575 | } | |
1576 | ||
1577 | /* DST = A ^ B */ | |
2f925a60 | 1578 | |
b6e72c17 | 1579 | void |
056755a1 | 1580 | bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b) |
b6e72c17 | 1581 | { |
1582 | bitmap_element *dst_elt = dst->first; | |
056755a1 | 1583 | const bitmap_element *a_elt = a->first; |
1584 | const bitmap_element *b_elt = b->first; | |
b6e72c17 | 1585 | bitmap_element *dst_prev = NULL; |
1586 | ||
07913396 | 1587 | gcc_assert (dst != a && dst != b); |
1588 | if (a == b) | |
1589 | { | |
1590 | bitmap_clear (dst); | |
1591 | return; | |
1592 | } | |
1593 | ||
b6e72c17 | 1594 | while (a_elt || b_elt) |
2f925a60 | 1595 | { |
b6e72c17 | 1596 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) |
1f3233d1 | 1597 | { |
b6e72c17 | 1598 | /* Matching elts, generate A ^ B. */ |
1599 | unsigned ix; | |
1600 | BITMAP_WORD ior = 0; | |
1601 | ||
1602 | if (!dst_elt) | |
5669bd62 | 1603 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); |
1604 | else | |
1605 | dst_elt->indx = a_elt->indx; | |
4399d500 | 1606 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 1607 | { |
1608 | BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; | |
1609 | ||
1610 | ior |= r; | |
1611 | dst_elt->bits[ix] = r; | |
1612 | } | |
1613 | a_elt = a_elt->next; | |
1614 | b_elt = b_elt->next; | |
1615 | if (ior) | |
1616 | { | |
1617 | dst_prev = dst_elt; | |
1618 | dst_elt = dst_elt->next; | |
1619 | } | |
1f3233d1 | 1620 | } |
1621 | else | |
1622 | { | |
b6e72c17 | 1623 | /* Copy a single element. */ |
056755a1 | 1624 | const bitmap_element *src; |
b6e72c17 | 1625 | |
1626 | if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
1627 | { | |
1628 | src = a_elt; | |
1629 | a_elt = a_elt->next; | |
1630 | } | |
1631 | else | |
1632 | { | |
1633 | src = b_elt; | |
1634 | b_elt = b_elt->next; | |
1635 | } | |
1636 | ||
1637 | if (!dst_elt) | |
5669bd62 | 1638 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx); |
a0c938f0 | 1639 | else |
5669bd62 | 1640 | dst_elt->indx = src->indx; |
b6e72c17 | 1641 | memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); |
1642 | dst_prev = dst_elt; | |
1643 | dst_elt = dst_elt->next; | |
1f3233d1 | 1644 | } |
2f925a60 | 1645 | } |
c926c35f | 1646 | /* Ensure that dst->current is valid. */ |
1647 | dst->current = dst->first; | |
b6e72c17 | 1648 | bitmap_elt_clear_from (dst, dst_elt); |
0ea2d350 | 1649 | gcc_checking_assert (!dst->current == !dst->first); |
b6e72c17 | 1650 | if (dst->current) |
1651 | dst->indx = dst->current->indx; | |
1652 | } | |
2f925a60 | 1653 | |
b6e72c17 | 1654 | /* A ^= B */ |
66b5ac3c | 1655 | |
b6e72c17 | 1656 | void |
056755a1 | 1657 | bitmap_xor_into (bitmap a, const_bitmap b) |
b6e72c17 | 1658 | { |
1659 | bitmap_element *a_elt = a->first; | |
056755a1 | 1660 | const bitmap_element *b_elt = b->first; |
b6e72c17 | 1661 | bitmap_element *a_prev = NULL; |
1662 | ||
07913396 | 1663 | if (a == b) |
1664 | { | |
1665 | bitmap_clear (a); | |
1666 | return; | |
1667 | } | |
1668 | ||
b6e72c17 | 1669 | while (b_elt) |
1670 | { | |
1671 | if (!a_elt || b_elt->indx < a_elt->indx) | |
1672 | { | |
1673 | /* Copy b_elt. */ | |
5669bd62 | 1674 | bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx); |
b6e72c17 | 1675 | memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); |
1676 | a_prev = dst; | |
1677 | b_elt = b_elt->next; | |
1678 | } | |
1679 | else if (a_elt->indx < b_elt->indx) | |
1680 | { | |
1681 | a_prev = a_elt; | |
1682 | a_elt = a_elt->next; | |
1683 | } | |
1684 | else | |
1685 | { | |
1686 | /* Matching elts, generate A ^= B. */ | |
1687 | unsigned ix; | |
1688 | BITMAP_WORD ior = 0; | |
1689 | bitmap_element *next = a_elt->next; | |
1690 | ||
4399d500 | 1691 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 1692 | { |
1693 | BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; | |
1694 | ||
1695 | ior |= r; | |
1696 | a_elt->bits[ix] = r; | |
1697 | } | |
1698 | b_elt = b_elt->next; | |
1699 | if (ior) | |
1700 | a_prev = a_elt; | |
1701 | else | |
1702 | bitmap_element_free (a, a_elt); | |
1703 | a_elt = next; | |
1704 | } | |
1705 | } | |
0ea2d350 | 1706 | gcc_checking_assert (!a->current == !a->first); |
b6e72c17 | 1707 | if (a->current) |
1708 | a->indx = a->current->indx; | |
66b5ac3c | 1709 | } |
1710 | ||
21576831 | 1711 | /* Return true if two bitmaps are identical. |
1712 | We do not bother with a check for pointer equality, as that never | |
1713 | occurs in practice. */ | |
66b5ac3c | 1714 | |
21576831 | 1715 | bool |
056755a1 | 1716 | bitmap_equal_p (const_bitmap a, const_bitmap b) |
66b5ac3c | 1717 | { |
056755a1 | 1718 | const bitmap_element *a_elt; |
1719 | const bitmap_element *b_elt; | |
21576831 | 1720 | unsigned ix; |
a0c938f0 | 1721 | |
21576831 | 1722 | for (a_elt = a->first, b_elt = b->first; |
1723 | a_elt && b_elt; | |
1724 | a_elt = a_elt->next, b_elt = b_elt->next) | |
1725 | { | |
1726 | if (a_elt->indx != b_elt->indx) | |
1727 | return false; | |
4399d500 | 1728 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
21576831 | 1729 | if (a_elt->bits[ix] != b_elt->bits[ix]) |
1730 | return false; | |
1731 | } | |
1732 | return !a_elt && !b_elt; | |
1733 | } | |
1734 | ||
1735 | /* Return true if A AND B is not empty. */ | |
1736 | ||
1737 | bool | |
056755a1 | 1738 | bitmap_intersect_p (const_bitmap a, const_bitmap b) |
21576831 | 1739 | { |
056755a1 | 1740 | const bitmap_element *a_elt; |
1741 | const bitmap_element *b_elt; | |
21576831 | 1742 | unsigned ix; |
a0c938f0 | 1743 | |
21576831 | 1744 | for (a_elt = a->first, b_elt = b->first; |
1745 | a_elt && b_elt;) | |
1746 | { | |
1747 | if (a_elt->indx < b_elt->indx) | |
1748 | a_elt = a_elt->next; | |
1749 | else if (b_elt->indx < a_elt->indx) | |
1750 | b_elt = b_elt->next; | |
1751 | else | |
1752 | { | |
4399d500 | 1753 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
21576831 | 1754 | if (a_elt->bits[ix] & b_elt->bits[ix]) |
1755 | return true; | |
1756 | a_elt = a_elt->next; | |
1757 | b_elt = b_elt->next; | |
1758 | } | |
1759 | } | |
1760 | return false; | |
1761 | } | |
66b5ac3c | 1762 | |
21576831 | 1763 | /* Return true if A AND NOT B is not empty. */ |
66b5ac3c | 1764 | |
21576831 | 1765 | bool |
056755a1 | 1766 | bitmap_intersect_compl_p (const_bitmap a, const_bitmap b) |
21576831 | 1767 | { |
056755a1 | 1768 | const bitmap_element *a_elt; |
1769 | const bitmap_element *b_elt; | |
21576831 | 1770 | unsigned ix; |
1771 | for (a_elt = a->first, b_elt = b->first; | |
1772 | a_elt && b_elt;) | |
1773 | { | |
1774 | if (a_elt->indx < b_elt->indx) | |
1775 | return true; | |
1776 | else if (b_elt->indx < a_elt->indx) | |
1777 | b_elt = b_elt->next; | |
1778 | else | |
1779 | { | |
4399d500 | 1780 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
21576831 | 1781 | if (a_elt->bits[ix] & ~b_elt->bits[ix]) |
1782 | return true; | |
1783 | a_elt = a_elt->next; | |
1784 | b_elt = b_elt->next; | |
1785 | } | |
1786 | } | |
1787 | return a_elt != NULL; | |
2f925a60 | 1788 | } |
21576831 | 1789 | |
2f925a60 | 1790 | \f |
b6e72c17 | 1791 | /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */ |
2f925a60 | 1792 | |
79d6d448 | 1793 | bool |
056755a1 | 1794 | bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill) |
2f925a60 | 1795 | { |
3072d30e | 1796 | bool changed = false; |
42fe97ed | 1797 | |
3072d30e | 1798 | bitmap_element *dst_elt = dst->first; |
056755a1 | 1799 | const bitmap_element *a_elt = a->first; |
1800 | const bitmap_element *b_elt = b->first; | |
1801 | const bitmap_element *kill_elt = kill->first; | |
3072d30e | 1802 | bitmap_element *dst_prev = NULL; |
1803 | bitmap_element **dst_prev_pnext = &dst->first; | |
1804 | ||
1805 | gcc_assert (dst != a && dst != b && dst != kill); | |
1806 | ||
1807 | /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */ | |
1808 | if (b == kill || bitmap_empty_p (b)) | |
1809 | { | |
1810 | changed = !bitmap_equal_p (dst, a); | |
1811 | if (changed) | |
1812 | bitmap_copy (dst, a); | |
1813 | return changed; | |
1814 | } | |
1815 | if (bitmap_empty_p (kill)) | |
1816 | return bitmap_ior (dst, a, b); | |
1817 | if (bitmap_empty_p (a)) | |
1818 | return bitmap_and_compl (dst, b, kill); | |
1819 | ||
1820 | while (a_elt || b_elt) | |
1821 | { | |
1822 | bool new_element = false; | |
1823 | ||
1824 | if (b_elt) | |
1825 | while (kill_elt && kill_elt->indx < b_elt->indx) | |
1826 | kill_elt = kill_elt->next; | |
1827 | ||
1828 | if (b_elt && kill_elt && kill_elt->indx == b_elt->indx | |
1829 | && (!a_elt || a_elt->indx >= b_elt->indx)) | |
1830 | { | |
1831 | bitmap_element tmp_elt; | |
1832 | unsigned ix; | |
1833 | ||
1834 | BITMAP_WORD ior = 0; | |
1835 | tmp_elt.indx = b_elt->indx; | |
4399d500 | 1836 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 1837 | { |
1838 | BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix]; | |
1839 | ior |= r; | |
1840 | tmp_elt.bits[ix] = r; | |
1841 | } | |
1842 | ||
1843 | if (ior) | |
1844 | { | |
1845 | changed = bitmap_elt_ior (dst, dst_elt, dst_prev, | |
1846 | a_elt, &tmp_elt, changed); | |
1847 | new_element = true; | |
1848 | if (a_elt && a_elt->indx == b_elt->indx) | |
1849 | a_elt = a_elt->next; | |
1850 | } | |
1851 | ||
1852 | b_elt = b_elt->next; | |
1853 | kill_elt = kill_elt->next; | |
1854 | } | |
1855 | else | |
1856 | { | |
1857 | changed = bitmap_elt_ior (dst, dst_elt, dst_prev, | |
1858 | a_elt, b_elt, changed); | |
1859 | new_element = true; | |
1860 | ||
1861 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) | |
1862 | { | |
1863 | a_elt = a_elt->next; | |
1864 | b_elt = b_elt->next; | |
1865 | } | |
1866 | else | |
1867 | { | |
1868 | if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) | |
1869 | a_elt = a_elt->next; | |
1870 | else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) | |
1871 | b_elt = b_elt->next; | |
1872 | } | |
1873 | } | |
1874 | ||
1875 | if (new_element) | |
1876 | { | |
1877 | dst_prev = *dst_prev_pnext; | |
1878 | dst_prev_pnext = &dst_prev->next; | |
1879 | dst_elt = *dst_prev_pnext; | |
1880 | } | |
1881 | } | |
1882 | ||
1883 | if (dst_elt) | |
1884 | { | |
1885 | changed = true; | |
85ac1c40 | 1886 | /* Ensure that dst->current is valid. */ |
1887 | dst->current = dst->first; | |
3072d30e | 1888 | bitmap_elt_clear_from (dst, dst_elt); |
1889 | } | |
0ea2d350 | 1890 | gcc_checking_assert (!dst->current == !dst->first); |
3072d30e | 1891 | if (dst->current) |
1892 | dst->indx = dst->current->indx; | |
b6e72c17 | 1893 | |
604efc01 | 1894 | return changed; |
2f925a60 | 1895 | } |
114c7df6 | 1896 | |
b6e72c17 | 1897 | /* A |= (FROM1 & ~FROM2). Return true if A changes. */ |
79d6d448 | 1898 | |
1899 | bool | |
056755a1 | 1900 | bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2) |
114c7df6 | 1901 | { |
1902 | bitmap_head tmp; | |
b6e72c17 | 1903 | bool changed; |
a0c938f0 | 1904 | |
42fe97ed | 1905 | bitmap_initialize (&tmp, &bitmap_default_obstack); |
b6e72c17 | 1906 | bitmap_and_compl (&tmp, from1, from2); |
1907 | changed = bitmap_ior_into (a, &tmp); | |
114c7df6 | 1908 | bitmap_clear (&tmp); |
1909 | ||
1910 | return changed; | |
1911 | } | |
3072d30e | 1912 | |
d7f2555b | 1913 | /* A |= (B & C). Return true if A changes. */ |
1914 | ||
1915 | bool | |
1916 | bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c) | |
1917 | { | |
1918 | bitmap_element *a_elt = a->first; | |
1919 | const bitmap_element *b_elt = b->first; | |
1920 | const bitmap_element *c_elt = c->first; | |
1921 | bitmap_element and_elt; | |
1922 | bitmap_element *a_prev = NULL; | |
1923 | bitmap_element **a_prev_pnext = &a->first; | |
1924 | bool changed = false; | |
1925 | unsigned ix; | |
1926 | ||
1927 | if (b == c) | |
1928 | return bitmap_ior_into (a, b); | |
1929 | if (bitmap_empty_p (b) || bitmap_empty_p (c)) | |
1930 | return false; | |
1931 | ||
1932 | and_elt.indx = -1; | |
1933 | while (b_elt && c_elt) | |
1934 | { | |
1935 | BITMAP_WORD overall; | |
1936 | ||
1937 | /* Find a common item of B and C. */ | |
1938 | while (b_elt->indx != c_elt->indx) | |
1939 | { | |
1940 | if (b_elt->indx < c_elt->indx) | |
1941 | { | |
1942 | b_elt = b_elt->next; | |
1943 | if (!b_elt) | |
1944 | goto done; | |
1945 | } | |
1946 | else | |
1947 | { | |
1948 | c_elt = c_elt->next; | |
1949 | if (!c_elt) | |
1950 | goto done; | |
1951 | } | |
1952 | } | |
1953 | ||
1954 | overall = 0; | |
1955 | and_elt.indx = b_elt->indx; | |
4399d500 | 1956 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
d7f2555b | 1957 | { |
1958 | and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix]; | |
1959 | overall |= and_elt.bits[ix]; | |
1960 | } | |
1961 | ||
1962 | b_elt = b_elt->next; | |
1963 | c_elt = c_elt->next; | |
1964 | if (!overall) | |
1965 | continue; | |
1966 | ||
1967 | /* Now find a place to insert AND_ELT. */ | |
1968 | do | |
1969 | { | |
1970 | ix = a_elt ? a_elt->indx : and_elt.indx; | |
1971 | if (ix == and_elt.indx) | |
1972 | changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed); | |
1973 | else if (ix > and_elt.indx) | |
1974 | changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed); | |
1975 | ||
1976 | a_prev = *a_prev_pnext; | |
1977 | a_prev_pnext = &a_prev->next; | |
1978 | a_elt = *a_prev_pnext; | |
1979 | ||
1980 | /* If A lagged behind B/C, we advanced it so loop once more. */ | |
1981 | } | |
1982 | while (ix < and_elt.indx); | |
1983 | } | |
1984 | ||
1985 | done: | |
0ea2d350 | 1986 | gcc_checking_assert (!a->current == !a->first); |
d7f2555b | 1987 | if (a->current) |
1988 | a->indx = a->current->indx; | |
1989 | return changed; | |
1990 | } | |
ecd52ea9 | 1991 | |
1992 | /* Compute hash of bitmap (for purposes of hashing). */ | |
1993 | hashval_t | |
1994 | bitmap_hash (const_bitmap head) | |
1995 | { | |
1996 | const bitmap_element *ptr; | |
1997 | BITMAP_WORD hash = 0; | |
1998 | int ix; | |
1999 | ||
2000 | for (ptr = head->first; ptr; ptr = ptr->next) | |
2001 | { | |
2002 | hash ^= ptr->indx; | |
2003 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
2004 | hash ^= ptr->bits[ix]; | |
2005 | } | |
2006 | return (hashval_t)hash; | |
2007 | } | |
2008 | ||
2f925a60 | 2009 | \f |
2f925a60 | 2010 | /* Debugging function to print out the contents of a bitmap. */ |
2011 | ||
4b987fac | 2012 | DEBUG_FUNCTION void |
056755a1 | 2013 | debug_bitmap_file (FILE *file, const_bitmap head) |
2f925a60 | 2014 | { |
056755a1 | 2015 | const bitmap_element *ptr; |
2f925a60 | 2016 | |
038ca0d1 | 2017 | fprintf (file, "\nfirst = " HOST_PTR_PRINTF |
2018 | " current = " HOST_PTR_PRINTF " indx = %u\n", | |
6f817829 | 2019 | (void *) head->first, (void *) head->current, head->indx); |
2f925a60 | 2020 | |
2021 | for (ptr = head->first; ptr; ptr = ptr->next) | |
2022 | { | |
e5c8f082 | 2023 | unsigned int i, j, col = 26; |
2f925a60 | 2024 | |
038ca0d1 | 2025 | fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF |
2026 | " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {", | |
056755a1 | 2027 | (const void*) ptr, (const void*) ptr->next, |
2028 | (const void*) ptr->prev, ptr->indx); | |
2f925a60 | 2029 | |
2030 | for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
e5c8f082 | 2031 | for (j = 0; j < BITMAP_WORD_BITS; j++) |
66b5ac3c | 2032 | if ((ptr->bits[i] >> j) & 1) |
2f925a60 | 2033 | { |
2034 | if (col > 70) | |
2035 | { | |
2036 | fprintf (file, "\n\t\t\t"); | |
2037 | col = 24; | |
2038 | } | |
2039 | ||
2040 | fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS | |
e5c8f082 | 2041 | + i * BITMAP_WORD_BITS + j)); |
2f925a60 | 2042 | col += 4; |
2043 | } | |
2044 | ||
2045 | fprintf (file, " }\n"); | |
2046 | } | |
2047 | } | |
ca2968e9 | 2048 | |
2f925a60 | 2049 | /* Function to be called from the debugger to print the contents |
2050 | of a bitmap. */ | |
2051 | ||
4b987fac | 2052 | DEBUG_FUNCTION void |
056755a1 | 2053 | debug_bitmap (const_bitmap head) |
2f925a60 | 2054 | { |
d72243e8 | 2055 | debug_bitmap_file (stderr, head); |
2f925a60 | 2056 | } |
ca2968e9 | 2057 | |
64c25516 | 2058 | /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file, |
23ec99a1 | 2059 | it does not print anything but the bits. */ |
2060 | ||
4b987fac | 2061 | DEBUG_FUNCTION void |
c7d89805 | 2062 | bitmap_print (FILE *file, const_bitmap head, const char *prefix, |
2063 | const char *suffix) | |
23ec99a1 | 2064 | { |
ba1d8f67 | 2065 | const char *comma = ""; |
4f917ffe | 2066 | unsigned i; |
0cc4271a | 2067 | bitmap_iterator bi; |
23ec99a1 | 2068 | |
2069 | fputs (prefix, file); | |
0cc4271a | 2070 | EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi) |
2071 | { | |
2072 | fprintf (file, "%s%d", comma, i); | |
2073 | comma = ", "; | |
2074 | } | |
23ec99a1 | 2075 | fputs (suffix, file); |
2076 | } | |
f65ffe0d | 2077 | |
f65ffe0d | 2078 | /* Output per-bitmap memory usage statistics. */ |
2079 | void | |
2080 | dump_bitmap_statistics (void) | |
2081 | { | |
ecd52ea9 | 2082 | if (! GATHER_STATISTICS) |
2083 | return; | |
2084 | ||
0ff42de5 | 2085 | bitmap_mem_desc.dump (BITMAP); |
844ea20e | 2086 | } |
2087 | ||
c7d89805 | 2088 | DEBUG_FUNCTION void |
b3e7c666 | 2089 | debug (const bitmap_head &ref) |
c7d89805 | 2090 | { |
2091 | dump_bitmap (stderr, &ref); | |
2092 | } | |
2093 | ||
2094 | DEBUG_FUNCTION void | |
b3e7c666 | 2095 | debug (const bitmap_head *ptr) |
c7d89805 | 2096 | { |
2097 | if (ptr) | |
2098 | debug (*ptr); | |
2099 | else | |
2100 | fprintf (stderr, "<nil>\n"); | |
2101 | } | |
2102 | ||
2103 | ||
1f3233d1 | 2104 | #include "gt-bitmap.h" |