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