Mercurial > hg > CbC > CbC_gcc
comparison gcc/bitmap.c @ 131:84e7813d76e9
gcc-8.2
author | mir3636 |
---|---|
date | Thu, 25 Oct 2018 07:37:49 +0900 |
parents | 04ced10e8804 |
children | 1830386684a0 |
comparison
equal
deleted
inserted
replaced
111:04ced10e8804 | 131:84e7813d76e9 |
---|---|
1 /* Functions to support general ended bitmaps. | 1 /* Functions to support general ended bitmaps. |
2 Copyright (C) 1997-2017 Free Software Foundation, Inc. | 2 Copyright (C) 1997-2018 Free Software Foundation, Inc. |
3 | 3 |
4 This file is part of GCC. | 4 This file is part of GCC. |
5 | 5 |
6 GCC is free software; you can redistribute it and/or modify it under | 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 | 7 the terms of the GNU General Public License as published by the Free |
23 #include "bitmap.h" | 23 #include "bitmap.h" |
24 #include "selftest.h" | 24 #include "selftest.h" |
25 | 25 |
26 /* Memory allocation statistics purpose instance. */ | 26 /* Memory allocation statistics purpose instance. */ |
27 mem_alloc_description<bitmap_usage> bitmap_mem_desc; | 27 mem_alloc_description<bitmap_usage> bitmap_mem_desc; |
28 | |
29 static bitmap_element *bitmap_tree_listify_from (bitmap, bitmap_element *); | |
28 | 30 |
29 /* Register new bitmap. */ | 31 /* Register new bitmap. */ |
30 void | 32 void |
31 bitmap_register (bitmap b MEM_STAT_DECL) | 33 bitmap_register (bitmap b MEM_STAT_DECL) |
32 { | 34 { |
47 bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */ | 49 bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */ |
48 static int bitmap_default_obstack_depth; | 50 static int bitmap_default_obstack_depth; |
49 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of | 51 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of |
50 GC'd elements. */ | 52 GC'd elements. */ |
51 | 53 |
52 static void bitmap_elem_to_freelist (bitmap, bitmap_element *); | |
53 static void bitmap_element_free (bitmap, bitmap_element *); | |
54 static bitmap_element *bitmap_element_allocate (bitmap); | |
55 static int bitmap_element_zerop (const bitmap_element *); | |
56 static void bitmap_element_link (bitmap, bitmap_element *); | |
57 static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int); | |
58 static void bitmap_elt_clear_from (bitmap, bitmap_element *); | |
59 static bitmap_element *bitmap_find_bit (bitmap, unsigned int); | |
60 | 54 |
61 | 55 /* Bitmap memory management. */ |
62 /* Add ELEM to the appropriate freelist. */ | 56 |
57 /* Add ELT to the appropriate freelist. */ | |
63 static inline void | 58 static inline void |
64 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt) | 59 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt) |
65 { | 60 { |
66 bitmap_obstack *bit_obstack = head->obstack; | 61 bitmap_obstack *bit_obstack = head->obstack; |
62 | |
63 if (GATHER_STATISTICS) | |
64 register_overhead (head, -((int)sizeof (bitmap_element))); | |
67 | 65 |
68 elt->next = NULL; | 66 elt->next = NULL; |
69 elt->indx = -1; | 67 elt->indx = -1; |
70 if (bit_obstack) | 68 if (bit_obstack) |
71 { | 69 { |
77 elt->prev = bitmap_ggc_free; | 75 elt->prev = bitmap_ggc_free; |
78 bitmap_ggc_free = elt; | 76 bitmap_ggc_free = elt; |
79 } | 77 } |
80 } | 78 } |
81 | 79 |
82 /* Free a bitmap element. Since these are allocated off the | |
83 bitmap_obstack, "free" actually means "put onto the freelist". */ | |
84 | |
85 static inline void | |
86 bitmap_element_free (bitmap head, bitmap_element *elt) | |
87 { | |
88 bitmap_element *next = elt->next; | |
89 bitmap_element *prev = elt->prev; | |
90 | |
91 if (prev) | |
92 prev->next = next; | |
93 | |
94 if (next) | |
95 next->prev = prev; | |
96 | |
97 if (head->first == elt) | |
98 head->first = next; | |
99 | |
100 /* Since the first thing we try is to insert before current, | |
101 make current the next entry in preference to the previous. */ | |
102 if (head->current == elt) | |
103 { | |
104 head->current = next != 0 ? next : prev; | |
105 if (head->current) | |
106 head->indx = head->current->indx; | |
107 else | |
108 head->indx = 0; | |
109 } | |
110 | |
111 if (GATHER_STATISTICS) | |
112 register_overhead (head, -((int)sizeof (bitmap_element))); | |
113 | |
114 bitmap_elem_to_freelist (head, elt); | |
115 } | |
116 | |
117 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */ | 80 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */ |
118 | 81 |
119 static inline bitmap_element * | 82 static inline bitmap_element * |
120 bitmap_element_allocate (bitmap head) | 83 bitmap_element_allocate (bitmap head) |
121 { | 84 { |
164 memset (element->bits, 0, sizeof (element->bits)); | 127 memset (element->bits, 0, sizeof (element->bits)); |
165 | 128 |
166 return element; | 129 return element; |
167 } | 130 } |
168 | 131 |
169 /* Remove ELT and all following elements from bitmap HEAD. */ | 132 /* Remove ELT and all following elements from bitmap HEAD. |
133 Put the released elements in the freelist for HEAD. */ | |
170 | 134 |
171 void | 135 void |
172 bitmap_elt_clear_from (bitmap head, bitmap_element *elt) | 136 bitmap_elt_clear_from (bitmap head, bitmap_element *elt) |
173 { | 137 { |
174 bitmap_element *prev; | 138 bitmap_element *prev; |
175 bitmap_obstack *bit_obstack = head->obstack; | 139 bitmap_obstack *bit_obstack = head->obstack; |
176 | 140 |
177 if (!elt) return; | 141 if (!elt) |
142 return; | |
143 | |
144 if (head->tree_form) | |
145 elt = bitmap_tree_listify_from (head, elt); | |
178 | 146 |
179 if (GATHER_STATISTICS) | 147 if (GATHER_STATISTICS) |
180 { | 148 { |
181 int n = 0; | 149 int n = 0; |
182 for (prev = elt; prev; prev = prev->next) | 150 for (prev = elt; prev; prev = prev->next) |
199 head->first = NULL; | 167 head->first = NULL; |
200 head->current = NULL; | 168 head->current = NULL; |
201 head->indx = 0; | 169 head->indx = 0; |
202 } | 170 } |
203 | 171 |
204 /* Put the entire list onto the free list in one operation. */ | 172 /* Put the entire list onto the freelist in one operation. */ |
205 if (bit_obstack) | 173 if (bit_obstack) |
206 { | 174 { |
207 elt->prev = bit_obstack->elements; | 175 elt->prev = bit_obstack->elements; |
208 bit_obstack->elements = elt; | 176 bit_obstack->elements = elt; |
209 } | 177 } |
211 { | 179 { |
212 elt->prev = bitmap_ggc_free; | 180 elt->prev = bitmap_ggc_free; |
213 bitmap_ggc_free = elt; | 181 bitmap_ggc_free = elt; |
214 } | 182 } |
215 } | 183 } |
216 | |
217 /* Clear a bitmap by freeing the linked list. */ | |
218 | |
219 void | |
220 bitmap_clear (bitmap head) | |
221 { | |
222 if (head->first) | |
223 bitmap_elt_clear_from (head, head->first); | |
224 } | |
225 | 184 |
226 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize | 185 /* Linked-list view of bitmaps. |
227 the default bitmap obstack. */ | 186 |
228 | 187 In this representation, the bitmap elements form a double-linked list |
229 void | 188 with elements sorted by increasing index. */ |
230 bitmap_obstack_initialize (bitmap_obstack *bit_obstack) | 189 |
231 { | |
232 if (!bit_obstack) | |
233 { | |
234 if (bitmap_default_obstack_depth++) | |
235 return; | |
236 bit_obstack = &bitmap_default_obstack; | |
237 } | |
238 | |
239 #if !defined(__GNUC__) || (__GNUC__ < 2) | |
240 #define __alignof__(type) 0 | |
241 #endif | |
242 | |
243 bit_obstack->elements = NULL; | |
244 bit_obstack->heads = NULL; | |
245 obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE, | |
246 __alignof__ (bitmap_element), | |
247 obstack_chunk_alloc, | |
248 obstack_chunk_free); | |
249 } | |
250 | |
251 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL, | |
252 release the default bitmap obstack. */ | |
253 | |
254 void | |
255 bitmap_obstack_release (bitmap_obstack *bit_obstack) | |
256 { | |
257 if (!bit_obstack) | |
258 { | |
259 if (--bitmap_default_obstack_depth) | |
260 { | |
261 gcc_assert (bitmap_default_obstack_depth > 0); | |
262 return; | |
263 } | |
264 bit_obstack = &bitmap_default_obstack; | |
265 } | |
266 | |
267 bit_obstack->elements = NULL; | |
268 bit_obstack->heads = NULL; | |
269 obstack_free (&bit_obstack->obstack, NULL); | |
270 } | |
271 | |
272 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create | |
273 it on the default bitmap obstack. */ | |
274 | |
275 bitmap | |
276 bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL) | |
277 { | |
278 bitmap map; | |
279 | |
280 if (!bit_obstack) | |
281 bit_obstack = &bitmap_default_obstack; | |
282 map = bit_obstack->heads; | |
283 if (map) | |
284 bit_obstack->heads = (struct bitmap_head *) map->first; | |
285 else | |
286 map = XOBNEW (&bit_obstack->obstack, bitmap_head); | |
287 bitmap_initialize (map, bit_obstack PASS_MEM_STAT); | |
288 | |
289 if (GATHER_STATISTICS) | |
290 register_overhead (map, sizeof (bitmap_head)); | |
291 | |
292 return map; | |
293 } | |
294 | |
295 /* Create a new GCd bitmap. */ | |
296 | |
297 bitmap | |
298 bitmap_gc_alloc (ALONE_MEM_STAT_DECL) | |
299 { | |
300 bitmap map; | |
301 | |
302 map = ggc_alloc<bitmap_head> (); | |
303 bitmap_initialize (map, NULL PASS_MEM_STAT); | |
304 | |
305 if (GATHER_STATISTICS) | |
306 register_overhead (map, sizeof (bitmap_head)); | |
307 | |
308 return map; | |
309 } | |
310 | |
311 /* Release an obstack allocated bitmap. */ | |
312 | |
313 void | |
314 bitmap_obstack_free (bitmap map) | |
315 { | |
316 if (map) | |
317 { | |
318 bitmap_clear (map); | |
319 map->first = (bitmap_element *) map->obstack->heads; | |
320 | |
321 if (GATHER_STATISTICS) | |
322 register_overhead (map, -((int)sizeof (bitmap_head))); | |
323 | |
324 map->obstack->heads = map; | |
325 } | |
326 } | |
327 | |
328 | |
329 /* Return nonzero if all bits in an element are zero. */ | |
330 | |
331 static inline int | |
332 bitmap_element_zerop (const bitmap_element *element) | |
333 { | |
334 #if BITMAP_ELEMENT_WORDS == 2 | |
335 return (element->bits[0] | element->bits[1]) == 0; | |
336 #else | |
337 unsigned i; | |
338 | |
339 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
340 if (element->bits[i] != 0) | |
341 return 0; | |
342 | |
343 return 1; | |
344 #endif | |
345 } | |
346 | |
347 /* Link the bitmap element into the current bitmap linked list. */ | 190 /* Link the bitmap element into the current bitmap linked list. */ |
348 | 191 |
349 static inline void | 192 static inline void |
350 bitmap_element_link (bitmap head, bitmap_element *element) | 193 bitmap_list_link_element (bitmap head, bitmap_element *element) |
351 { | 194 { |
352 unsigned int indx = element->indx; | 195 unsigned int indx = element->indx; |
353 bitmap_element *ptr; | 196 bitmap_element *ptr; |
197 | |
198 gcc_checking_assert (!head->tree_form); | |
354 | 199 |
355 /* If this is the first and only element, set it in. */ | 200 /* If this is the first and only element, set it in. */ |
356 if (head->first == 0) | 201 if (head->first == 0) |
357 { | 202 { |
358 element->next = element->prev = 0; | 203 element->next = element->prev = 0; |
397 /* Set up so this is the first element searched. */ | 242 /* Set up so this is the first element searched. */ |
398 head->current = element; | 243 head->current = element; |
399 head->indx = indx; | 244 head->indx = indx; |
400 } | 245 } |
401 | 246 |
247 /* Unlink the bitmap element from the current bitmap linked list, | |
248 and return it to the freelist. */ | |
249 | |
250 static inline void | |
251 bitmap_list_unlink_element (bitmap head, bitmap_element *element) | |
252 { | |
253 bitmap_element *next = element->next; | |
254 bitmap_element *prev = element->prev; | |
255 | |
256 gcc_checking_assert (!head->tree_form); | |
257 | |
258 if (prev) | |
259 prev->next = next; | |
260 | |
261 if (next) | |
262 next->prev = prev; | |
263 | |
264 if (head->first == element) | |
265 head->first = next; | |
266 | |
267 /* Since the first thing we try is to insert before current, | |
268 make current the next entry in preference to the previous. */ | |
269 if (head->current == element) | |
270 { | |
271 head->current = next != 0 ? next : prev; | |
272 if (head->current) | |
273 head->indx = head->current->indx; | |
274 else | |
275 head->indx = 0; | |
276 } | |
277 | |
278 bitmap_elem_to_freelist (head, element); | |
279 } | |
280 | |
402 /* Insert a new uninitialized element into bitmap HEAD after element | 281 /* Insert a new uninitialized element into bitmap HEAD after element |
403 ELT. If ELT is NULL, insert the element at the start. Return the | 282 ELT. If ELT is NULL, insert the element at the start. Return the |
404 new element. */ | 283 new element. */ |
405 | 284 |
406 static bitmap_element * | 285 static bitmap_element * |
407 bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx) | 286 bitmap_list_insert_element_after (bitmap head, |
287 bitmap_element *elt, unsigned int indx) | |
408 { | 288 { |
409 bitmap_element *node = bitmap_element_allocate (head); | 289 bitmap_element *node = bitmap_element_allocate (head); |
410 node->indx = indx; | 290 node->indx = indx; |
291 | |
292 gcc_checking_assert (!head->tree_form); | |
411 | 293 |
412 if (!elt) | 294 if (!elt) |
413 { | 295 { |
414 if (!head->current) | 296 if (!head->current) |
415 { | 297 { |
431 elt->next = node; | 313 elt->next = node; |
432 node->prev = elt; | 314 node->prev = elt; |
433 } | 315 } |
434 return node; | 316 return node; |
435 } | 317 } |
436 | 318 |
437 /* Copy a bitmap to another bitmap. */ | 319 /* Return the element for INDX, or NULL if the element doesn't exist. |
438 | 320 Update the `current' field even if we can't find an element that |
439 void | |
440 bitmap_copy (bitmap to, const_bitmap from) | |
441 { | |
442 const bitmap_element *from_ptr; | |
443 bitmap_element *to_ptr = 0; | |
444 | |
445 bitmap_clear (to); | |
446 | |
447 /* Copy elements in forward direction one at a time. */ | |
448 for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next) | |
449 { | |
450 bitmap_element *to_elt = bitmap_element_allocate (to); | |
451 | |
452 to_elt->indx = from_ptr->indx; | |
453 memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits)); | |
454 | |
455 /* Here we have a special case of bitmap_element_link, for the case | |
456 where we know the links are being entered in sequence. */ | |
457 if (to_ptr == 0) | |
458 { | |
459 to->first = to->current = to_elt; | |
460 to->indx = from_ptr->indx; | |
461 to_elt->next = to_elt->prev = 0; | |
462 } | |
463 else | |
464 { | |
465 to_elt->prev = to_ptr; | |
466 to_elt->next = 0; | |
467 to_ptr->next = to_elt; | |
468 } | |
469 | |
470 to_ptr = to_elt; | |
471 } | |
472 } | |
473 | |
474 /* Move a bitmap to another bitmap. */ | |
475 | |
476 void | |
477 bitmap_move (bitmap to, bitmap from) | |
478 { | |
479 gcc_assert (to->obstack == from->obstack); | |
480 | |
481 bitmap_clear (to); | |
482 | |
483 *to = *from; | |
484 | |
485 if (GATHER_STATISTICS) | |
486 { | |
487 size_t sz = 0; | |
488 for (bitmap_element *e = to->first; e; e = e->next) | |
489 sz += sizeof (bitmap_element); | |
490 register_overhead (to, sz); | |
491 register_overhead (from, -sz); | |
492 } | |
493 } | |
494 | |
495 /* Find a bitmap element that would hold a bitmap's bit. | |
496 Update the `current' field even if we can't find an element that | |
497 would hold the bitmap's bit to make eventual allocation | 321 would hold the bitmap's bit to make eventual allocation |
498 faster. */ | 322 faster. */ |
499 | 323 |
500 static inline bitmap_element * | 324 static inline bitmap_element * |
501 bitmap_find_bit (bitmap head, unsigned int bit) | 325 bitmap_list_find_element (bitmap head, unsigned int indx) |
502 { | 326 { |
503 bitmap_element *element; | 327 bitmap_element *element; |
504 unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; | |
505 | 328 |
506 if (head->current == NULL | 329 if (head->current == NULL |
507 || head->indx == indx) | 330 || head->indx == indx) |
508 return head->current; | 331 return head->current; |
332 | |
509 if (head->current == head->first | 333 if (head->current == head->first |
510 && head->first->next == NULL) | 334 && head->first->next == NULL) |
511 return NULL; | 335 return NULL; |
512 | 336 |
513 /* Usage can be NULL due to allocated bitmaps for which we do not | 337 /* Usage can be NULL due to allocated bitmaps for which we do not |
547 /* INDX is less than head->indx and closer to 0 than to | 371 /* INDX is less than head->indx and closer to 0 than to |
548 head->indx. Search from head->first forward. */ | 372 head->indx. Search from head->first forward. */ |
549 for (element = head->first; | 373 for (element = head->first; |
550 element->next != 0 && element->indx < indx; | 374 element->next != 0 && element->indx < indx; |
551 element = element->next) | 375 element = element->next) |
552 if (GATHER_STATISTICS && usage) | 376 { |
553 { | 377 if (GATHER_STATISTICS && usage) |
554 usage->m_search_iter++; | 378 usage->m_search_iter++; |
555 } | 379 } |
556 | 380 |
557 /* `element' is the nearest to the one we want. If it's not the one we | 381 /* `element' is the nearest to the one we want. If it's not the one we |
558 want, the one we want doesn't exist. */ | 382 want, the one we want doesn't exist. */ |
383 gcc_checking_assert (element != NULL); | |
559 head->current = element; | 384 head->current = element; |
560 head->indx = element->indx; | 385 head->indx = element->indx; |
561 if (element->indx != indx) | 386 if (element->indx != indx) |
562 element = 0; | 387 element = 0; |
563 | |
564 return element; | 388 return element; |
389 } | |
390 | |
391 | |
392 /* Splay-tree view of bitmaps. | |
393 | |
394 This is an almost one-to-one the implementatin of the simple top-down | |
395 splay tree in Sleator and Tarjan's "Self-adjusting Binary Search Trees". | |
396 It is probably not the most efficient form of splay trees, but it should | |
397 be good enough to experiment with this idea of bitmaps-as-trees. | |
398 | |
399 For all functions below, the variable or function argument "t" is a node | |
400 in the tree, and "e" is a temporary or new node in the tree. The rest | |
401 is sufficiently straigh-forward (and very well explained in the paper) | |
402 that comment would only clutter things. */ | |
403 | |
404 static inline void | |
405 bitmap_tree_link_left (bitmap_element * &t, bitmap_element * &l) | |
406 { | |
407 l->next = t; | |
408 l = t; | |
409 t = t->next; | |
410 } | |
411 | |
412 static inline void | |
413 bitmap_tree_link_right (bitmap_element * &t, bitmap_element * &r) | |
414 { | |
415 r->prev = t; | |
416 r = t; | |
417 t = t->prev; | |
418 } | |
419 | |
420 static inline void | |
421 bitmap_tree_rotate_left (bitmap_element * &t) | |
422 { | |
423 bitmap_element *e = t->next; | |
424 t->next = t->next->prev; | |
425 e->prev = t; | |
426 t = e; | |
427 } | |
428 | |
429 static inline void | |
430 bitmap_tree_rotate_right (bitmap_element * &t) | |
431 { | |
432 bitmap_element *e = t->prev; | |
433 t->prev = t->prev->next; | |
434 e->next = t; | |
435 t = e; | |
436 } | |
437 | |
438 static bitmap_element * | |
439 bitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx) | |
440 { | |
441 bitmap_element N, *l, *r; | |
442 | |
443 if (t == NULL) | |
444 return NULL; | |
445 | |
446 bitmap_usage *usage = NULL; | |
447 if (GATHER_STATISTICS) | |
448 usage = bitmap_mem_desc.get_descriptor_for_instance (head); | |
449 | |
450 N.prev = N.next = NULL; | |
451 l = r = &N; | |
452 | |
453 while (indx != t->indx) | |
454 { | |
455 if (GATHER_STATISTICS && usage) | |
456 usage->m_search_iter++; | |
457 | |
458 if (indx < t->indx) | |
459 { | |
460 if (t->prev != NULL && indx < t->prev->indx) | |
461 bitmap_tree_rotate_right (t); | |
462 if (t->prev == NULL) | |
463 break; | |
464 bitmap_tree_link_right (t, r); | |
465 } | |
466 else if (indx > t->indx) | |
467 { | |
468 if (t->next != NULL && indx > t->next->indx) | |
469 bitmap_tree_rotate_left (t); | |
470 if (t->next == NULL) | |
471 break; | |
472 bitmap_tree_link_left (t, l); | |
473 } | |
474 } | |
475 | |
476 l->next = t->prev; | |
477 r->prev = t->next; | |
478 t->prev = N.next; | |
479 t->next = N.prev; | |
480 return t; | |
481 } | |
482 | |
483 /* Link bitmap element E into the current bitmap splay tree. */ | |
484 | |
485 static inline void | |
486 bitmap_tree_link_element (bitmap head, bitmap_element *e) | |
487 { | |
488 if (head->first == NULL) | |
489 e->prev = e->next = NULL; | |
490 else | |
491 { | |
492 bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx); | |
493 if (e->indx < t->indx) | |
494 { | |
495 e->prev = t->prev; | |
496 e->next = t; | |
497 t->prev = NULL; | |
498 } | |
499 else if (e->indx > t->indx) | |
500 { | |
501 e->next = t->next; | |
502 e->prev = t; | |
503 t->next = NULL; | |
504 } | |
505 else | |
506 gcc_unreachable (); | |
507 } | |
508 head->first = e; | |
509 head->current = e; | |
510 head->indx = e->indx; | |
511 } | |
512 | |
513 /* Unlink bitmap element E from the current bitmap splay tree, | |
514 and return it to the freelist. */ | |
515 | |
516 static void | |
517 bitmap_tree_unlink_element (bitmap head, bitmap_element *e) | |
518 { | |
519 bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx); | |
520 | |
521 gcc_checking_assert (t == e); | |
522 | |
523 if (e->prev == NULL) | |
524 t = e->next; | |
525 else | |
526 { | |
527 t = bitmap_tree_splay (head, e->prev, e->indx); | |
528 t->next = e->next; | |
529 } | |
530 head->first = t; | |
531 head->current = t; | |
532 head->indx = (t != NULL) ? t->indx : 0; | |
533 | |
534 bitmap_elem_to_freelist (head, e); | |
535 } | |
536 | |
537 /* Return the element for INDX, or NULL if the element doesn't exist. */ | |
538 | |
539 static inline bitmap_element * | |
540 bitmap_tree_find_element (bitmap head, unsigned int indx) | |
541 { | |
542 if (head->current == NULL | |
543 || head->indx == indx) | |
544 return head->current; | |
545 | |
546 /* Usage can be NULL due to allocated bitmaps for which we do not | |
547 call initialize function. */ | |
548 bitmap_usage *usage = NULL; | |
549 if (GATHER_STATISTICS) | |
550 usage = bitmap_mem_desc.get_descriptor_for_instance (head); | |
551 | |
552 /* This bitmap has more than one element, and we're going to look | |
553 through the elements list. Count that as a search. */ | |
554 if (GATHER_STATISTICS && usage) | |
555 usage->m_nsearches++; | |
556 | |
557 bitmap_element *element = bitmap_tree_splay (head, head->first, indx); | |
558 gcc_checking_assert (element != NULL); | |
559 head->first = element; | |
560 head->current = element; | |
561 head->indx = element->indx; | |
562 if (element->indx != indx) | |
563 element = 0; | |
564 return element; | |
565 } | |
566 | |
567 /* Converting bitmap views from linked-list to tree and vice versa. */ | |
568 | |
569 /* Splice element E and all elements with a larger index from | |
570 bitmap HEAD, convert the spliced elements to the linked-list | |
571 view, and return the head of the list (which should be E again), */ | |
572 | |
573 static bitmap_element * | |
574 bitmap_tree_listify_from (bitmap head, bitmap_element *e) | |
575 { | |
576 bitmap_element *t, *erb; | |
577 | |
578 /* Detach the right branch from E (all elements with indx > E->indx), | |
579 and splay E to the root. */ | |
580 erb = e->next; | |
581 e->next = NULL; | |
582 t = bitmap_tree_splay (head, head->first, e->indx); | |
583 gcc_checking_assert (t == e); | |
584 | |
585 /* Because E has no right branch, and we rotated it to the root, | |
586 the left branch is the new root. */ | |
587 t = e->prev; | |
588 head->first = t; | |
589 head->current = t; | |
590 head->indx = (t != NULL) ? t->indx : 0; | |
591 | |
592 /* Detach the tree from E, and re-attach the right branch of E. */ | |
593 e->prev = NULL; | |
594 e->next = erb; | |
595 | |
596 /* The tree is now valid again. Now we need to "un-tree" E. | |
597 It is imperative that a non-recursive implementation is used | |
598 for this, because splay trees have a worst case depth of O(N) | |
599 for a tree with N nodes. A recursive implementation could | |
600 result in a stack overflow for a sufficiently large, unbalanced | |
601 bitmap tree. */ | |
602 | |
603 auto_vec<bitmap_element *, 32> stack; | |
604 auto_vec<bitmap_element *, 32> sorted_elements; | |
605 bitmap_element *n = e; | |
606 | |
607 while (true) | |
608 { | |
609 while (n != NULL) | |
610 { | |
611 stack.safe_push (n); | |
612 n = n->prev; | |
613 } | |
614 | |
615 if (stack.is_empty ()) | |
616 break; | |
617 | |
618 n = stack.pop (); | |
619 sorted_elements.safe_push (n); | |
620 n = n->next; | |
621 } | |
622 | |
623 gcc_assert (sorted_elements[0] == e); | |
624 | |
625 bitmap_element *prev = NULL; | |
626 unsigned ix; | |
627 FOR_EACH_VEC_ELT (sorted_elements, ix, n) | |
628 { | |
629 if (prev != NULL) | |
630 prev->next = n; | |
631 n->prev = prev; | |
632 n->next = NULL; | |
633 prev = n; | |
634 } | |
635 | |
636 return e; | |
637 } | |
638 | |
639 /* Convert bitmap HEAD from splay-tree view to linked-list view. */ | |
640 | |
641 void | |
642 bitmap_list_view (bitmap head) | |
643 { | |
644 bitmap_element *ptr; | |
645 | |
646 gcc_assert (head->tree_form); | |
647 | |
648 ptr = head->first; | |
649 if (ptr) | |
650 { | |
651 while (ptr->prev) | |
652 bitmap_tree_rotate_right (ptr); | |
653 head->first = ptr; | |
654 head->first = bitmap_tree_listify_from (head, ptr); | |
655 } | |
656 | |
657 head->tree_form = false; | |
658 } | |
659 | |
660 /* Convert bitmap HEAD from linked-list view to splay-tree view. | |
661 This is simply a matter of dropping the prev or next pointers | |
662 and setting the tree_form flag. The tree will balance itself | |
663 if and when it is used. */ | |
664 | |
665 void | |
666 bitmap_tree_view (bitmap head) | |
667 { | |
668 bitmap_element *ptr; | |
669 | |
670 gcc_assert (! head->tree_form); | |
671 | |
672 ptr = head->first; | |
673 while (ptr) | |
674 { | |
675 ptr->prev = NULL; | |
676 ptr = ptr->next; | |
677 } | |
678 | |
679 head->tree_form = true; | |
680 } | |
681 | |
682 /* Clear a bitmap by freeing all its elements. */ | |
683 | |
684 void | |
685 bitmap_clear (bitmap head) | |
686 { | |
687 if (head->first == NULL) | |
688 return; | |
689 if (head->tree_form) | |
690 { | |
691 bitmap_element *e, *t; | |
692 for (e = head->first; e->prev; e = e->prev) | |
693 /* Loop to find the element with the smallest index. */ ; | |
694 t = bitmap_tree_splay (head, head->first, e->indx); | |
695 gcc_checking_assert (t == e); | |
696 head->first = t; | |
697 } | |
698 bitmap_elt_clear_from (head, head->first); | |
699 } | |
700 | |
701 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize | |
702 the default bitmap obstack. */ | |
703 | |
704 void | |
705 bitmap_obstack_initialize (bitmap_obstack *bit_obstack) | |
706 { | |
707 if (!bit_obstack) | |
708 { | |
709 if (bitmap_default_obstack_depth++) | |
710 return; | |
711 bit_obstack = &bitmap_default_obstack; | |
712 } | |
713 | |
714 #if !defined(__GNUC__) || (__GNUC__ < 2) | |
715 #define __alignof__(type) 0 | |
716 #endif | |
717 | |
718 bit_obstack->elements = NULL; | |
719 bit_obstack->heads = NULL; | |
720 obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE, | |
721 __alignof__ (bitmap_element), | |
722 obstack_chunk_alloc, | |
723 obstack_chunk_free); | |
724 } | |
725 | |
726 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL, | |
727 release the default bitmap obstack. */ | |
728 | |
729 void | |
730 bitmap_obstack_release (bitmap_obstack *bit_obstack) | |
731 { | |
732 if (!bit_obstack) | |
733 { | |
734 if (--bitmap_default_obstack_depth) | |
735 { | |
736 gcc_assert (bitmap_default_obstack_depth > 0); | |
737 return; | |
738 } | |
739 bit_obstack = &bitmap_default_obstack; | |
740 } | |
741 | |
742 bit_obstack->elements = NULL; | |
743 bit_obstack->heads = NULL; | |
744 obstack_free (&bit_obstack->obstack, NULL); | |
745 } | |
746 | |
747 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create | |
748 it on the default bitmap obstack. */ | |
749 | |
750 bitmap | |
751 bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL) | |
752 { | |
753 bitmap map; | |
754 | |
755 if (!bit_obstack) | |
756 bit_obstack = &bitmap_default_obstack; | |
757 map = bit_obstack->heads; | |
758 if (map) | |
759 bit_obstack->heads = (struct bitmap_head *) map->first; | |
760 else | |
761 map = XOBNEW (&bit_obstack->obstack, bitmap_head); | |
762 bitmap_initialize (map, bit_obstack PASS_MEM_STAT); | |
763 | |
764 if (GATHER_STATISTICS) | |
765 register_overhead (map, sizeof (bitmap_head)); | |
766 | |
767 return map; | |
768 } | |
769 | |
770 /* Create a new GCd bitmap. */ | |
771 | |
772 bitmap | |
773 bitmap_gc_alloc (ALONE_MEM_STAT_DECL) | |
774 { | |
775 bitmap map; | |
776 | |
777 map = ggc_alloc<bitmap_head> (); | |
778 bitmap_initialize (map, NULL PASS_MEM_STAT); | |
779 | |
780 if (GATHER_STATISTICS) | |
781 register_overhead (map, sizeof (bitmap_head)); | |
782 | |
783 return map; | |
784 } | |
785 | |
786 /* Release an obstack allocated bitmap. */ | |
787 | |
788 void | |
789 bitmap_obstack_free (bitmap map) | |
790 { | |
791 if (map) | |
792 { | |
793 bitmap_clear (map); | |
794 map->first = (bitmap_element *) map->obstack->heads; | |
795 | |
796 if (GATHER_STATISTICS) | |
797 register_overhead (map, -((int)sizeof (bitmap_head))); | |
798 | |
799 map->obstack->heads = map; | |
800 } | |
801 } | |
802 | |
803 | |
804 /* Return nonzero if all bits in an element are zero. */ | |
805 | |
806 static inline int | |
807 bitmap_element_zerop (const bitmap_element *element) | |
808 { | |
809 #if BITMAP_ELEMENT_WORDS == 2 | |
810 return (element->bits[0] | element->bits[1]) == 0; | |
811 #else | |
812 unsigned i; | |
813 | |
814 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
815 if (element->bits[i] != 0) | |
816 return 0; | |
817 | |
818 return 1; | |
819 #endif | |
820 } | |
821 | |
822 /* Copy a bitmap to another bitmap. */ | |
823 | |
824 void | |
825 bitmap_copy (bitmap to, const_bitmap from) | |
826 { | |
827 const bitmap_element *from_ptr; | |
828 bitmap_element *to_ptr = 0; | |
829 | |
830 gcc_checking_assert (!to->tree_form && !from->tree_form); | |
831 | |
832 bitmap_clear (to); | |
833 | |
834 /* Copy elements in forward direction one at a time. */ | |
835 for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next) | |
836 { | |
837 bitmap_element *to_elt = bitmap_element_allocate (to); | |
838 | |
839 to_elt->indx = from_ptr->indx; | |
840 memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits)); | |
841 | |
842 /* Here we have a special case of bitmap_list_link_element, | |
843 for the case where we know the links are being entered | |
844 in sequence. */ | |
845 if (to_ptr == 0) | |
846 { | |
847 to->first = to->current = to_elt; | |
848 to->indx = from_ptr->indx; | |
849 to_elt->next = to_elt->prev = 0; | |
850 } | |
851 else | |
852 { | |
853 to_elt->prev = to_ptr; | |
854 to_elt->next = 0; | |
855 to_ptr->next = to_elt; | |
856 } | |
857 | |
858 to_ptr = to_elt; | |
859 } | |
860 } | |
861 | |
862 /* Move a bitmap to another bitmap. */ | |
863 | |
864 void | |
865 bitmap_move (bitmap to, bitmap from) | |
866 { | |
867 gcc_assert (to->obstack == from->obstack); | |
868 | |
869 bitmap_clear (to); | |
870 | |
871 *to = *from; | |
872 | |
873 if (GATHER_STATISTICS) | |
874 { | |
875 size_t sz = 0; | |
876 for (bitmap_element *e = to->first; e; e = e->next) | |
877 sz += sizeof (bitmap_element); | |
878 register_overhead (to, sz); | |
879 register_overhead (from, -sz); | |
880 } | |
565 } | 881 } |
566 | 882 |
567 /* Clear a single bit in a bitmap. Return true if the bit changed. */ | 883 /* Clear a single bit in a bitmap. Return true if the bit changed. */ |
568 | 884 |
569 bool | 885 bool |
570 bitmap_clear_bit (bitmap head, int bit) | 886 bitmap_clear_bit (bitmap head, int bit) |
571 { | 887 { |
572 bitmap_element *const ptr = bitmap_find_bit (head, bit); | 888 unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; |
573 | 889 bitmap_element *ptr; |
890 | |
891 if (!head->tree_form) | |
892 ptr = bitmap_list_find_element (head, indx); | |
893 else | |
894 ptr = bitmap_tree_find_element (head, indx); | |
574 if (ptr != 0) | 895 if (ptr != 0) |
575 { | 896 { |
576 unsigned bit_num = bit % BITMAP_WORD_BITS; | 897 unsigned bit_num = bit % BITMAP_WORD_BITS; |
577 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | 898 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; |
578 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; | 899 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; |
581 { | 902 { |
582 ptr->bits[word_num] &= ~bit_val; | 903 ptr->bits[word_num] &= ~bit_val; |
583 /* If we cleared the entire word, free up the element. */ | 904 /* If we cleared the entire word, free up the element. */ |
584 if (!ptr->bits[word_num] | 905 if (!ptr->bits[word_num] |
585 && bitmap_element_zerop (ptr)) | 906 && bitmap_element_zerop (ptr)) |
586 bitmap_element_free (head, ptr); | 907 { |
908 if (!head->tree_form) | |
909 bitmap_list_unlink_element (head, ptr); | |
910 else | |
911 bitmap_tree_unlink_element (head, ptr); | |
912 } | |
587 } | 913 } |
588 | 914 |
589 return res; | 915 return res; |
590 } | 916 } |
591 | 917 |
595 /* Set a single bit in a bitmap. Return true if the bit changed. */ | 921 /* Set a single bit in a bitmap. Return true if the bit changed. */ |
596 | 922 |
597 bool | 923 bool |
598 bitmap_set_bit (bitmap head, int bit) | 924 bitmap_set_bit (bitmap head, int bit) |
599 { | 925 { |
600 bitmap_element *ptr = bitmap_find_bit (head, bit); | 926 unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS; |
927 bitmap_element *ptr; | |
928 if (!head->tree_form) | |
929 ptr = bitmap_list_find_element (head, indx); | |
930 else | |
931 ptr = bitmap_tree_find_element (head, indx); | |
601 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | 932 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; |
602 unsigned bit_num = bit % BITMAP_WORD_BITS; | 933 unsigned bit_num = bit % BITMAP_WORD_BITS; |
603 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; | 934 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; |
604 | 935 |
605 if (ptr == 0) | 936 if (ptr != 0) |
606 { | |
607 ptr = bitmap_element_allocate (head); | |
608 ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; | |
609 ptr->bits[word_num] = bit_val; | |
610 bitmap_element_link (head, ptr); | |
611 return true; | |
612 } | |
613 else | |
614 { | 937 { |
615 bool res = (ptr->bits[word_num] & bit_val) == 0; | 938 bool res = (ptr->bits[word_num] & bit_val) == 0; |
616 if (res) | 939 if (res) |
617 ptr->bits[word_num] |= bit_val; | 940 ptr->bits[word_num] |= bit_val; |
618 return res; | 941 return res; |
619 } | 942 } |
943 | |
944 ptr = bitmap_element_allocate (head); | |
945 ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; | |
946 ptr->bits[word_num] = bit_val; | |
947 if (!head->tree_form) | |
948 bitmap_list_link_element (head, ptr); | |
949 else | |
950 bitmap_tree_link_element (head, ptr); | |
951 return true; | |
620 } | 952 } |
621 | 953 |
622 /* Return whether a bit is set within a bitmap. */ | 954 /* Return whether a bit is set within a bitmap. */ |
623 | 955 |
624 int | 956 int |
625 bitmap_bit_p (bitmap head, int bit) | 957 bitmap_bit_p (bitmap head, int bit) |
626 { | 958 { |
959 unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; | |
627 bitmap_element *ptr; | 960 bitmap_element *ptr; |
628 unsigned bit_num; | 961 unsigned bit_num; |
629 unsigned word_num; | 962 unsigned word_num; |
630 | 963 |
631 ptr = bitmap_find_bit (head, bit); | 964 if (!head->tree_form) |
965 ptr = bitmap_list_find_element (head, indx); | |
966 else | |
967 ptr = bitmap_tree_find_element (head, indx); | |
632 if (ptr == 0) | 968 if (ptr == 0) |
633 return 0; | 969 return 0; |
634 | 970 |
635 bit_num = bit % BITMAP_WORD_BITS; | 971 bit_num = bit % BITMAP_WORD_BITS; |
636 word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | 972 word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; |
690 bitmap_count_bits (const_bitmap a) | 1026 bitmap_count_bits (const_bitmap a) |
691 { | 1027 { |
692 unsigned long count = 0; | 1028 unsigned long count = 0; |
693 const bitmap_element *elt; | 1029 const bitmap_element *elt; |
694 | 1030 |
1031 gcc_checking_assert (!a->tree_form); | |
695 for (elt = a->first; elt; elt = elt->next) | 1032 for (elt = a->first; elt; elt = elt->next) |
696 count += bitmap_count_bits_in_word (elt->bits); | 1033 count += bitmap_count_bits_in_word (elt->bits); |
697 | 1034 |
698 return count; | 1035 return count; |
699 } | 1036 } |
746 | 1083 |
747 if (bitmap_empty_p (a)) | 1084 if (bitmap_empty_p (a)) |
748 return false; | 1085 return false; |
749 | 1086 |
750 elt = a->first; | 1087 elt = a->first; |
1088 | |
751 /* As there are no completely empty bitmap elements, a second one | 1089 /* As there are no completely empty bitmap elements, a second one |
752 means we have more than one bit set. */ | 1090 means we have more than one bit set. */ |
753 if (elt->next != NULL) | 1091 if (elt->next != NULL |
1092 && (!a->tree_form || elt->prev != NULL)) | |
754 return false; | 1093 return false; |
755 | 1094 |
756 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | 1095 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) |
757 { | 1096 { |
758 #if GCC_VERSION >= 3400 | 1097 #if GCC_VERSION >= 3400 |
780 unsigned bit_no; | 1119 unsigned bit_no; |
781 BITMAP_WORD word; | 1120 BITMAP_WORD word; |
782 unsigned ix; | 1121 unsigned ix; |
783 | 1122 |
784 gcc_checking_assert (elt); | 1123 gcc_checking_assert (elt); |
1124 | |
1125 if (a->tree_form) | |
1126 while (elt->prev) | |
1127 elt = elt->prev; | |
1128 | |
785 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; | 1129 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; |
786 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | 1130 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) |
787 { | 1131 { |
788 word = elt->bits[ix]; | 1132 word = elt->bits[ix]; |
789 if (word) | 1133 if (word) |
825 bitmap must be non-empty. */ | 1169 bitmap must be non-empty. */ |
826 | 1170 |
827 unsigned | 1171 unsigned |
828 bitmap_last_set_bit (const_bitmap a) | 1172 bitmap_last_set_bit (const_bitmap a) |
829 { | 1173 { |
830 const bitmap_element *elt = a->current ? a->current : a->first; | 1174 const bitmap_element *elt; |
831 unsigned bit_no; | 1175 unsigned bit_no; |
832 BITMAP_WORD word; | 1176 BITMAP_WORD word; |
833 int ix; | 1177 int ix; |
834 | 1178 |
1179 if (a->tree_form) | |
1180 elt = a->first; | |
1181 else | |
1182 elt = a->current ? a->current : a->first; | |
835 gcc_checking_assert (elt); | 1183 gcc_checking_assert (elt); |
1184 | |
836 while (elt->next) | 1185 while (elt->next) |
837 elt = elt->next; | 1186 elt = elt->next; |
1187 | |
838 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; | 1188 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; |
839 for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--) | 1189 for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--) |
840 { | 1190 { |
841 word = elt->bits[ix]; | 1191 word = elt->bits[ix]; |
842 if (word) | 1192 if (word) |
874 bitmap_element *dst_elt = dst->first; | 1224 bitmap_element *dst_elt = dst->first; |
875 const bitmap_element *a_elt = a->first; | 1225 const bitmap_element *a_elt = a->first; |
876 const bitmap_element *b_elt = b->first; | 1226 const bitmap_element *b_elt = b->first; |
877 bitmap_element *dst_prev = NULL; | 1227 bitmap_element *dst_prev = NULL; |
878 | 1228 |
1229 gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form); | |
879 gcc_assert (dst != a && dst != b); | 1230 gcc_assert (dst != a && dst != b); |
880 | 1231 |
881 if (a == b) | 1232 if (a == b) |
882 { | 1233 { |
883 bitmap_copy (dst, a); | 1234 bitmap_copy (dst, a); |
895 /* Matching elts, generate A & B. */ | 1246 /* Matching elts, generate A & B. */ |
896 unsigned ix; | 1247 unsigned ix; |
897 BITMAP_WORD ior = 0; | 1248 BITMAP_WORD ior = 0; |
898 | 1249 |
899 if (!dst_elt) | 1250 if (!dst_elt) |
900 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | 1251 dst_elt = bitmap_list_insert_element_after (dst, dst_prev, |
1252 a_elt->indx); | |
901 else | 1253 else |
902 dst_elt->indx = a_elt->indx; | 1254 dst_elt->indx = a_elt->indx; |
903 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) | 1255 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
904 { | 1256 { |
905 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; | 1257 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; |
932 bitmap_element *a_elt = a->first; | 1284 bitmap_element *a_elt = a->first; |
933 const bitmap_element *b_elt = b->first; | 1285 const bitmap_element *b_elt = b->first; |
934 bitmap_element *next; | 1286 bitmap_element *next; |
935 bool changed = false; | 1287 bool changed = false; |
936 | 1288 |
1289 gcc_checking_assert (!a->tree_form && !b->tree_form); | |
1290 | |
937 if (a == b) | 1291 if (a == b) |
938 return false; | 1292 return false; |
939 | 1293 |
940 while (a_elt && b_elt) | 1294 while (a_elt && b_elt) |
941 { | 1295 { |
942 if (a_elt->indx < b_elt->indx) | 1296 if (a_elt->indx < b_elt->indx) |
943 { | 1297 { |
944 next = a_elt->next; | 1298 next = a_elt->next; |
945 bitmap_element_free (a, a_elt); | 1299 bitmap_list_unlink_element (a, a_elt); |
946 a_elt = next; | 1300 a_elt = next; |
947 changed = true; | 1301 changed = true; |
948 } | 1302 } |
949 else if (b_elt->indx < a_elt->indx) | 1303 else if (b_elt->indx < a_elt->indx) |
950 b_elt = b_elt->next; | 1304 b_elt = b_elt->next; |
962 a_elt->bits[ix] = r; | 1316 a_elt->bits[ix] = r; |
963 ior |= r; | 1317 ior |= r; |
964 } | 1318 } |
965 next = a_elt->next; | 1319 next = a_elt->next; |
966 if (!ior) | 1320 if (!ior) |
967 bitmap_element_free (a, a_elt); | 1321 bitmap_list_unlink_element (a, a_elt); |
968 a_elt = next; | 1322 a_elt = next; |
969 b_elt = b_elt->next; | 1323 b_elt = b_elt->next; |
970 } | 1324 } |
971 } | 1325 } |
972 | 1326 |
1004 } | 1358 } |
1005 else | 1359 else |
1006 { | 1360 { |
1007 changed = true; | 1361 changed = true; |
1008 if (!dst_elt) | 1362 if (!dst_elt) |
1009 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx); | 1363 dst_elt = bitmap_list_insert_element_after (dst, dst_prev, |
1364 src_elt->indx); | |
1010 else | 1365 else |
1011 dst_elt->indx = src_elt->indx; | 1366 dst_elt->indx = src_elt->indx; |
1012 memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits)); | 1367 memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits)); |
1013 } | 1368 } |
1014 return changed; | 1369 return changed; |
1026 const bitmap_element *b_elt = b->first; | 1381 const bitmap_element *b_elt = b->first; |
1027 bitmap_element *dst_prev = NULL; | 1382 bitmap_element *dst_prev = NULL; |
1028 bitmap_element **dst_prev_pnext = &dst->first; | 1383 bitmap_element **dst_prev_pnext = &dst->first; |
1029 bool changed = false; | 1384 bool changed = false; |
1030 | 1385 |
1386 gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form); | |
1031 gcc_assert (dst != a && dst != b); | 1387 gcc_assert (dst != a && dst != b); |
1032 | 1388 |
1033 if (a == b) | 1389 if (a == b) |
1034 { | 1390 { |
1035 changed = !bitmap_empty_p (dst); | 1391 changed = !bitmap_empty_p (dst); |
1074 else | 1430 else |
1075 { | 1431 { |
1076 bool new_element; | 1432 bool new_element; |
1077 if (!dst_elt || dst_elt->indx > a_elt->indx) | 1433 if (!dst_elt || dst_elt->indx > a_elt->indx) |
1078 { | 1434 { |
1079 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | 1435 dst_elt = bitmap_list_insert_element_after (dst, dst_prev, |
1436 a_elt->indx); | |
1080 new_element = true; | 1437 new_element = true; |
1081 } | 1438 } |
1082 else | 1439 else |
1083 { | 1440 { |
1084 dst_elt->indx = a_elt->indx; | 1441 dst_elt->indx = a_elt->indx; |
1096 if (ior) | 1453 if (ior) |
1097 changed = true; | 1454 changed = true; |
1098 else | 1455 else |
1099 { | 1456 { |
1100 changed |= !new_element; | 1457 changed |= !new_element; |
1101 bitmap_element_free (dst, dst_elt); | 1458 bitmap_list_unlink_element (dst, dst_elt); |
1102 dst_elt = *dst_prev_pnext; | 1459 dst_elt = *dst_prev_pnext; |
1103 } | 1460 } |
1104 } | 1461 } |
1105 | 1462 |
1106 if (ior) | 1463 if (ior) |
1136 { | 1493 { |
1137 bitmap_element *a_elt = a->first; | 1494 bitmap_element *a_elt = a->first; |
1138 const bitmap_element *b_elt = b->first; | 1495 const bitmap_element *b_elt = b->first; |
1139 bitmap_element *next; | 1496 bitmap_element *next; |
1140 BITMAP_WORD changed = 0; | 1497 BITMAP_WORD changed = 0; |
1498 | |
1499 gcc_checking_assert (!a->tree_form && !b->tree_form); | |
1141 | 1500 |
1142 if (a == b) | 1501 if (a == b) |
1143 { | 1502 { |
1144 if (bitmap_empty_p (a)) | 1503 if (bitmap_empty_p (a)) |
1145 return false; | 1504 return false; |
1171 changed |= cleared; | 1530 changed |= cleared; |
1172 ior |= r; | 1531 ior |= r; |
1173 } | 1532 } |
1174 next = a_elt->next; | 1533 next = a_elt->next; |
1175 if (!ior) | 1534 if (!ior) |
1176 bitmap_element_free (a, a_elt); | 1535 bitmap_list_unlink_element (a, a_elt); |
1177 a_elt = next; | 1536 a_elt = next; |
1178 b_elt = b_elt->next; | 1537 b_elt = b_elt->next; |
1179 } | 1538 } |
1180 } | 1539 } |
1181 gcc_checking_assert (!a->current == !a->first | 1540 gcc_checking_assert (!a->current == !a->first |
1189 { | 1548 { |
1190 unsigned int first_index, end_bit_plus1, last_index; | 1549 unsigned int first_index, end_bit_plus1, last_index; |
1191 bitmap_element *elt, *elt_prev; | 1550 bitmap_element *elt, *elt_prev; |
1192 unsigned int i; | 1551 unsigned int i; |
1193 | 1552 |
1553 gcc_checking_assert (!head->tree_form); | |
1554 | |
1194 if (!count) | 1555 if (!count) |
1195 return; | 1556 return; |
1196 | 1557 |
1197 if (count == 1) | 1558 if (count == 1) |
1198 { | 1559 { |
1201 } | 1562 } |
1202 | 1563 |
1203 first_index = start / BITMAP_ELEMENT_ALL_BITS; | 1564 first_index = start / BITMAP_ELEMENT_ALL_BITS; |
1204 end_bit_plus1 = start + count; | 1565 end_bit_plus1 = start + count; |
1205 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; | 1566 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; |
1206 elt = bitmap_find_bit (head, start); | 1567 elt = bitmap_list_find_element (head, first_index); |
1207 | 1568 |
1208 /* If bitmap_find_bit returns zero, the current is the closest block | 1569 /* If bitmap_list_find_element returns zero, the current is the closest block |
1209 to the result. Otherwise, just use bitmap_element_allocate to | 1570 to the result. Otherwise, just use bitmap_element_allocate to |
1210 ensure ELT is set; in the loop below, ELT == NULL means "insert | 1571 ensure ELT is set; in the loop below, ELT == NULL means "insert |
1211 at the end of the bitmap". */ | 1572 at the end of the bitmap". */ |
1212 if (!elt) | 1573 if (!elt) |
1213 { | 1574 { |
1214 elt = bitmap_element_allocate (head); | 1575 elt = bitmap_element_allocate (head); |
1215 elt->indx = first_index; | 1576 elt->indx = first_index; |
1216 bitmap_element_link (head, elt); | 1577 bitmap_list_link_element (head, elt); |
1217 } | 1578 } |
1218 | 1579 |
1219 gcc_checking_assert (elt->indx == first_index); | 1580 gcc_checking_assert (elt->indx == first_index); |
1220 elt_prev = elt->prev; | 1581 elt_prev = elt->prev; |
1221 for (i = first_index; i <= last_index; i++) | 1582 for (i = first_index; i <= last_index; i++) |
1228 unsigned int last_word_to_mod; | 1589 unsigned int last_word_to_mod; |
1229 BITMAP_WORD last_mask; | 1590 BITMAP_WORD last_mask; |
1230 unsigned int ix; | 1591 unsigned int ix; |
1231 | 1592 |
1232 if (!elt || elt->indx != i) | 1593 if (!elt || elt->indx != i) |
1233 elt = bitmap_elt_insert_after (head, elt_prev, i); | 1594 elt = bitmap_list_insert_element_after (head, elt_prev, i); |
1234 | 1595 |
1235 if (elt_start_bit <= start) | 1596 if (elt_start_bit <= start) |
1236 { | 1597 { |
1237 /* The first bit to turn on is somewhere inside this | 1598 /* The first bit to turn on is somewhere inside this |
1238 elt. */ | 1599 elt. */ |
1294 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count) | 1655 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count) |
1295 { | 1656 { |
1296 unsigned int first_index, end_bit_plus1, last_index; | 1657 unsigned int first_index, end_bit_plus1, last_index; |
1297 bitmap_element *elt; | 1658 bitmap_element *elt; |
1298 | 1659 |
1660 gcc_checking_assert (!head->tree_form); | |
1661 | |
1299 if (!count) | 1662 if (!count) |
1300 return; | 1663 return; |
1301 | 1664 |
1302 if (count == 1) | 1665 if (count == 1) |
1303 { | 1666 { |
1306 } | 1669 } |
1307 | 1670 |
1308 first_index = start / BITMAP_ELEMENT_ALL_BITS; | 1671 first_index = start / BITMAP_ELEMENT_ALL_BITS; |
1309 end_bit_plus1 = start + count; | 1672 end_bit_plus1 = start + count; |
1310 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; | 1673 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; |
1311 elt = bitmap_find_bit (head, start); | 1674 elt = bitmap_list_find_element (head, first_index); |
1312 | 1675 |
1313 /* If bitmap_find_bit returns zero, the current is the closest block | 1676 /* If bitmap_list_find_element returns zero, the current is the closest block |
1314 to the result. If the current is less than first index, find the | 1677 to the result. If the current is less than first index, find the |
1315 next one. Otherwise, just set elt to be current. */ | 1678 next one. Otherwise, just set elt to be current. */ |
1316 if (!elt) | 1679 if (!elt) |
1317 { | 1680 { |
1318 if (head->current) | 1681 if (head->current) |
1337 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; | 1700 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; |
1338 | 1701 |
1339 | 1702 |
1340 if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1) | 1703 if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1) |
1341 /* Get rid of the entire elt and go to the next one. */ | 1704 /* Get rid of the entire elt and go to the next one. */ |
1342 bitmap_element_free (head, elt); | 1705 bitmap_list_unlink_element (head, elt); |
1343 else | 1706 else |
1344 { | 1707 { |
1345 /* Going to have to knock out some bits in this elt. */ | 1708 /* Going to have to knock out some bits in this elt. */ |
1346 unsigned int first_word_to_mod; | 1709 unsigned int first_word_to_mod; |
1347 BITMAP_WORD first_mask; | 1710 BITMAP_WORD first_mask; |
1407 clear = false; | 1770 clear = false; |
1408 break; | 1771 break; |
1409 } | 1772 } |
1410 /* Check to see if there are any bits left. */ | 1773 /* Check to see if there are any bits left. */ |
1411 if (clear) | 1774 if (clear) |
1412 bitmap_element_free (head, elt); | 1775 bitmap_list_unlink_element (head, elt); |
1413 } | 1776 } |
1414 elt = next_elt; | 1777 elt = next_elt; |
1415 } | 1778 } |
1416 | 1779 |
1417 if (elt) | 1780 if (elt) |
1429 bitmap_element *a_elt = a->first; | 1792 bitmap_element *a_elt = a->first; |
1430 const bitmap_element *b_elt = b->first; | 1793 const bitmap_element *b_elt = b->first; |
1431 bitmap_element *a_prev = NULL; | 1794 bitmap_element *a_prev = NULL; |
1432 bitmap_element *next; | 1795 bitmap_element *next; |
1433 | 1796 |
1797 gcc_checking_assert (!a->tree_form && !b->tree_form); | |
1434 gcc_assert (a != b); | 1798 gcc_assert (a != b); |
1435 | 1799 |
1436 if (bitmap_empty_p (a)) | 1800 if (bitmap_empty_p (a)) |
1437 { | 1801 { |
1438 bitmap_copy (a, b); | 1802 bitmap_copy (a, b); |
1449 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | 1813 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) |
1450 { | 1814 { |
1451 /* A is before B. Remove A */ | 1815 /* A is before B. Remove A */ |
1452 next = a_elt->next; | 1816 next = a_elt->next; |
1453 a_prev = a_elt->prev; | 1817 a_prev = a_elt->prev; |
1454 bitmap_element_free (a, a_elt); | 1818 bitmap_list_unlink_element (a, a_elt); |
1455 a_elt = next; | 1819 a_elt = next; |
1456 } | 1820 } |
1457 else if (!a_elt || b_elt->indx < a_elt->indx) | 1821 else if (!a_elt || b_elt->indx < a_elt->indx) |
1458 { | 1822 { |
1459 /* B is before A. Copy B. */ | 1823 /* B is before A. Copy B. */ |
1460 next = bitmap_elt_insert_after (a, a_prev, b_elt->indx); | 1824 next = bitmap_list_insert_element_after (a, a_prev, b_elt->indx); |
1461 memcpy (next->bits, b_elt->bits, sizeof (next->bits)); | 1825 memcpy (next->bits, b_elt->bits, sizeof (next->bits)); |
1462 a_prev = next; | 1826 a_prev = next; |
1463 b_elt = b_elt->next; | 1827 b_elt = b_elt->next; |
1464 } | 1828 } |
1465 else | 1829 else |
1476 a_elt->bits[ix] = r; | 1840 a_elt->bits[ix] = r; |
1477 ior |= r; | 1841 ior |= r; |
1478 } | 1842 } |
1479 next = a_elt->next; | 1843 next = a_elt->next; |
1480 if (!ior) | 1844 if (!ior) |
1481 bitmap_element_free (a, a_elt); | 1845 bitmap_list_unlink_element (a, a_elt); |
1482 else | 1846 else |
1483 a_prev = a_elt; | 1847 a_prev = a_elt; |
1484 a_elt = next; | 1848 a_elt = next; |
1485 b_elt = b_elt->next; | 1849 b_elt = b_elt->next; |
1486 } | 1850 } |
1521 } | 1885 } |
1522 else | 1886 else |
1523 { | 1887 { |
1524 changed = true; | 1888 changed = true; |
1525 if (!dst_elt) | 1889 if (!dst_elt) |
1526 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | 1890 dst_elt = bitmap_list_insert_element_after (dst, dst_prev, |
1891 a_elt->indx); | |
1527 else | 1892 else |
1528 dst_elt->indx = a_elt->indx; | 1893 dst_elt->indx = a_elt->indx; |
1529 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) | 1894 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
1530 { | 1895 { |
1531 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; | 1896 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; |
1560 const bitmap_element *b_elt = b->first; | 1925 const bitmap_element *b_elt = b->first; |
1561 bitmap_element *dst_prev = NULL; | 1926 bitmap_element *dst_prev = NULL; |
1562 bitmap_element **dst_prev_pnext = &dst->first; | 1927 bitmap_element **dst_prev_pnext = &dst->first; |
1563 bool changed = false; | 1928 bool changed = false; |
1564 | 1929 |
1930 gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form); | |
1565 gcc_assert (dst != a && dst != b); | 1931 gcc_assert (dst != a && dst != b); |
1566 | 1932 |
1567 while (a_elt || b_elt) | 1933 while (a_elt || b_elt) |
1568 { | 1934 { |
1569 changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed); | 1935 changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed); |
1608 const bitmap_element *b_elt = b->first; | 1974 const bitmap_element *b_elt = b->first; |
1609 bitmap_element *a_prev = NULL; | 1975 bitmap_element *a_prev = NULL; |
1610 bitmap_element **a_prev_pnext = &a->first; | 1976 bitmap_element **a_prev_pnext = &a->first; |
1611 bool changed = false; | 1977 bool changed = false; |
1612 | 1978 |
1979 gcc_checking_assert (!a->tree_form && !b->tree_form); | |
1613 if (a == b) | 1980 if (a == b) |
1614 return false; | 1981 return false; |
1615 | 1982 |
1616 while (b_elt) | 1983 while (b_elt) |
1617 { | 1984 { |
1646 bitmap_element *dst_elt = dst->first; | 2013 bitmap_element *dst_elt = dst->first; |
1647 const bitmap_element *a_elt = a->first; | 2014 const bitmap_element *a_elt = a->first; |
1648 const bitmap_element *b_elt = b->first; | 2015 const bitmap_element *b_elt = b->first; |
1649 bitmap_element *dst_prev = NULL; | 2016 bitmap_element *dst_prev = NULL; |
1650 | 2017 |
2018 gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form); | |
1651 gcc_assert (dst != a && dst != b); | 2019 gcc_assert (dst != a && dst != b); |
2020 | |
1652 if (a == b) | 2021 if (a == b) |
1653 { | 2022 { |
1654 bitmap_clear (dst); | 2023 bitmap_clear (dst); |
1655 return; | 2024 return; |
1656 } | 2025 } |
1662 /* Matching elts, generate A ^ B. */ | 2031 /* Matching elts, generate A ^ B. */ |
1663 unsigned ix; | 2032 unsigned ix; |
1664 BITMAP_WORD ior = 0; | 2033 BITMAP_WORD ior = 0; |
1665 | 2034 |
1666 if (!dst_elt) | 2035 if (!dst_elt) |
1667 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | 2036 dst_elt = bitmap_list_insert_element_after (dst, dst_prev, |
2037 a_elt->indx); | |
1668 else | 2038 else |
1669 dst_elt->indx = a_elt->indx; | 2039 dst_elt->indx = a_elt->indx; |
1670 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) | 2040 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
1671 { | 2041 { |
1672 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; | 2042 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; |
1697 src = b_elt; | 2067 src = b_elt; |
1698 b_elt = b_elt->next; | 2068 b_elt = b_elt->next; |
1699 } | 2069 } |
1700 | 2070 |
1701 if (!dst_elt) | 2071 if (!dst_elt) |
1702 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx); | 2072 dst_elt = bitmap_list_insert_element_after (dst, dst_prev, |
2073 src->indx); | |
1703 else | 2074 else |
1704 dst_elt->indx = src->indx; | 2075 dst_elt->indx = src->indx; |
1705 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); | 2076 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); |
1706 dst_prev = dst_elt; | 2077 dst_prev = dst_elt; |
1707 dst_elt = dst_elt->next; | 2078 dst_elt = dst_elt->next; |
1722 { | 2093 { |
1723 bitmap_element *a_elt = a->first; | 2094 bitmap_element *a_elt = a->first; |
1724 const bitmap_element *b_elt = b->first; | 2095 const bitmap_element *b_elt = b->first; |
1725 bitmap_element *a_prev = NULL; | 2096 bitmap_element *a_prev = NULL; |
1726 | 2097 |
2098 gcc_checking_assert (!a->tree_form && !b->tree_form); | |
2099 | |
1727 if (a == b) | 2100 if (a == b) |
1728 { | 2101 { |
1729 bitmap_clear (a); | 2102 bitmap_clear (a); |
1730 return; | 2103 return; |
1731 } | 2104 } |
1733 while (b_elt) | 2106 while (b_elt) |
1734 { | 2107 { |
1735 if (!a_elt || b_elt->indx < a_elt->indx) | 2108 if (!a_elt || b_elt->indx < a_elt->indx) |
1736 { | 2109 { |
1737 /* Copy b_elt. */ | 2110 /* Copy b_elt. */ |
1738 bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx); | 2111 bitmap_element *dst = bitmap_list_insert_element_after (a, a_prev, |
2112 b_elt->indx); | |
1739 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); | 2113 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); |
1740 a_prev = dst; | 2114 a_prev = dst; |
1741 b_elt = b_elt->next; | 2115 b_elt = b_elt->next; |
1742 } | 2116 } |
1743 else if (a_elt->indx < b_elt->indx) | 2117 else if (a_elt->indx < b_elt->indx) |
1761 } | 2135 } |
1762 b_elt = b_elt->next; | 2136 b_elt = b_elt->next; |
1763 if (ior) | 2137 if (ior) |
1764 a_prev = a_elt; | 2138 a_prev = a_elt; |
1765 else | 2139 else |
1766 bitmap_element_free (a, a_elt); | 2140 bitmap_list_unlink_element (a, a_elt); |
1767 a_elt = next; | 2141 a_elt = next; |
1768 } | 2142 } |
1769 } | 2143 } |
1770 gcc_checking_assert (!a->current == !a->first); | 2144 gcc_checking_assert (!a->current == !a->first); |
1771 if (a->current) | 2145 if (a->current) |
1780 bitmap_equal_p (const_bitmap a, const_bitmap b) | 2154 bitmap_equal_p (const_bitmap a, const_bitmap b) |
1781 { | 2155 { |
1782 const bitmap_element *a_elt; | 2156 const bitmap_element *a_elt; |
1783 const bitmap_element *b_elt; | 2157 const bitmap_element *b_elt; |
1784 unsigned ix; | 2158 unsigned ix; |
2159 | |
2160 gcc_checking_assert (!a->tree_form && !b->tree_form); | |
1785 | 2161 |
1786 for (a_elt = a->first, b_elt = b->first; | 2162 for (a_elt = a->first, b_elt = b->first; |
1787 a_elt && b_elt; | 2163 a_elt && b_elt; |
1788 a_elt = a_elt->next, b_elt = b_elt->next) | 2164 a_elt = a_elt->next, b_elt = b_elt->next) |
1789 { | 2165 { |
1803 { | 2179 { |
1804 const bitmap_element *a_elt; | 2180 const bitmap_element *a_elt; |
1805 const bitmap_element *b_elt; | 2181 const bitmap_element *b_elt; |
1806 unsigned ix; | 2182 unsigned ix; |
1807 | 2183 |
2184 gcc_checking_assert (!a->tree_form && !b->tree_form); | |
2185 | |
1808 for (a_elt = a->first, b_elt = b->first; | 2186 for (a_elt = a->first, b_elt = b->first; |
1809 a_elt && b_elt;) | 2187 a_elt && b_elt;) |
1810 { | 2188 { |
1811 if (a_elt->indx < b_elt->indx) | 2189 if (a_elt->indx < b_elt->indx) |
1812 a_elt = a_elt->next; | 2190 a_elt = a_elt->next; |
1830 bitmap_intersect_compl_p (const_bitmap a, const_bitmap b) | 2208 bitmap_intersect_compl_p (const_bitmap a, const_bitmap b) |
1831 { | 2209 { |
1832 const bitmap_element *a_elt; | 2210 const bitmap_element *a_elt; |
1833 const bitmap_element *b_elt; | 2211 const bitmap_element *b_elt; |
1834 unsigned ix; | 2212 unsigned ix; |
2213 | |
2214 gcc_checking_assert (!a->tree_form && !b->tree_form); | |
2215 | |
1835 for (a_elt = a->first, b_elt = b->first; | 2216 for (a_elt = a->first, b_elt = b->first; |
1836 a_elt && b_elt;) | 2217 a_elt && b_elt;) |
1837 { | 2218 { |
1838 if (a_elt->indx < b_elt->indx) | 2219 if (a_elt->indx < b_elt->indx) |
1839 return true; | 2220 return true; |
1864 const bitmap_element *b_elt = b->first; | 2245 const bitmap_element *b_elt = b->first; |
1865 const bitmap_element *kill_elt = kill->first; | 2246 const bitmap_element *kill_elt = kill->first; |
1866 bitmap_element *dst_prev = NULL; | 2247 bitmap_element *dst_prev = NULL; |
1867 bitmap_element **dst_prev_pnext = &dst->first; | 2248 bitmap_element **dst_prev_pnext = &dst->first; |
1868 | 2249 |
2250 gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form | |
2251 && !kill->tree_form); | |
1869 gcc_assert (dst != a && dst != b && dst != kill); | 2252 gcc_assert (dst != a && dst != b && dst != kill); |
1870 | 2253 |
1871 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */ | 2254 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */ |
1872 if (b == kill || bitmap_empty_p (b)) | 2255 if (b == kill || bitmap_empty_p (b)) |
1873 { | 2256 { |
1956 dst->indx = dst->current->indx; | 2339 dst->indx = dst->current->indx; |
1957 | 2340 |
1958 return changed; | 2341 return changed; |
1959 } | 2342 } |
1960 | 2343 |
1961 /* A |= (FROM1 & ~FROM2). Return true if A changes. */ | 2344 /* A |= (B & ~C). Return true if A changes. */ |
1962 | 2345 |
1963 bool | 2346 bool |
1964 bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2) | 2347 bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c) |
1965 { | 2348 { |
1966 bitmap_head tmp; | 2349 bitmap_head tmp; |
1967 bool changed; | 2350 bool changed; |
1968 | 2351 |
2352 gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form); | |
2353 | |
1969 bitmap_initialize (&tmp, &bitmap_default_obstack); | 2354 bitmap_initialize (&tmp, &bitmap_default_obstack); |
1970 bitmap_and_compl (&tmp, from1, from2); | 2355 bitmap_and_compl (&tmp, b, c); |
1971 changed = bitmap_ior_into (a, &tmp); | 2356 changed = bitmap_ior_into (a, &tmp); |
1972 bitmap_clear (&tmp); | 2357 bitmap_clear (&tmp); |
1973 | 2358 |
1974 return changed; | 2359 return changed; |
1975 } | 2360 } |
1986 bitmap_element *a_prev = NULL; | 2371 bitmap_element *a_prev = NULL; |
1987 bitmap_element **a_prev_pnext = &a->first; | 2372 bitmap_element **a_prev_pnext = &a->first; |
1988 bool changed = false; | 2373 bool changed = false; |
1989 unsigned ix; | 2374 unsigned ix; |
1990 | 2375 |
2376 gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form); | |
2377 | |
1991 if (b == c) | 2378 if (b == c) |
1992 return bitmap_ior_into (a, b); | 2379 return bitmap_ior_into (a, b); |
1993 if (bitmap_empty_p (b) || bitmap_empty_p (c)) | 2380 if (bitmap_empty_p (b) || bitmap_empty_p (c)) |
1994 return false; | 2381 return false; |
1995 | 2382 |
2052 a->indx = a->current->indx; | 2439 a->indx = a->current->indx; |
2053 return changed; | 2440 return changed; |
2054 } | 2441 } |
2055 | 2442 |
2056 /* Compute hash of bitmap (for purposes of hashing). */ | 2443 /* Compute hash of bitmap (for purposes of hashing). */ |
2444 | |
2057 hashval_t | 2445 hashval_t |
2058 bitmap_hash (const_bitmap head) | 2446 bitmap_hash (const_bitmap head) |
2059 { | 2447 { |
2060 const bitmap_element *ptr; | 2448 const bitmap_element *ptr; |
2061 BITMAP_WORD hash = 0; | 2449 BITMAP_WORD hash = 0; |
2062 int ix; | 2450 int ix; |
2063 | 2451 |
2452 gcc_checking_assert (!head->tree_form); | |
2453 | |
2064 for (ptr = head->first; ptr; ptr = ptr->next) | 2454 for (ptr = head->first; ptr; ptr = ptr->next) |
2065 { | 2455 { |
2066 hash ^= ptr->indx; | 2456 hash ^= ptr->indx; |
2067 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | 2457 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) |
2068 hash ^= ptr->bits[ix]; | 2458 hash ^= ptr->bits[ix]; |
2069 } | 2459 } |
2070 return (hashval_t)hash; | 2460 return (hashval_t)hash; |
2071 } | 2461 } |
2072 | 2462 |
2073 | 2463 |
2464 /* Function to obtain a vector of bitmap elements in bit order from | |
2465 HEAD in tree view. */ | |
2466 | |
2467 static void | |
2468 bitmap_tree_to_vec (vec<bitmap_element *> &elts, const_bitmap head) | |
2469 { | |
2470 gcc_checking_assert (head->tree_form); | |
2471 auto_vec<bitmap_element *, 32> stack; | |
2472 bitmap_element *e = head->first; | |
2473 while (true) | |
2474 { | |
2475 while (e != NULL) | |
2476 { | |
2477 stack.safe_push (e); | |
2478 e = e->prev; | |
2479 } | |
2480 if (stack.is_empty ()) | |
2481 break; | |
2482 | |
2483 e = stack.pop (); | |
2484 elts.safe_push (e); | |
2485 e = e->next; | |
2486 } | |
2487 } | |
2488 | |
2489 /* Debugging function to print out the contents of a bitmap element. */ | |
2490 | |
2491 DEBUG_FUNCTION void | |
2492 debug_bitmap_elt_file (FILE *file, const bitmap_element *ptr) | |
2493 { | |
2494 unsigned int i, j, col = 26; | |
2495 | |
2496 fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF | |
2497 " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {", | |
2498 (const void*) ptr, (const void*) ptr->next, | |
2499 (const void*) ptr->prev, ptr->indx); | |
2500 | |
2501 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
2502 for (j = 0; j < BITMAP_WORD_BITS; j++) | |
2503 if ((ptr->bits[i] >> j) & 1) | |
2504 { | |
2505 if (col > 70) | |
2506 { | |
2507 fprintf (file, "\n\t\t\t"); | |
2508 col = 24; | |
2509 } | |
2510 | |
2511 fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS | |
2512 + i * BITMAP_WORD_BITS + j)); | |
2513 col += 4; | |
2514 } | |
2515 | |
2516 fprintf (file, " }\n"); | |
2517 } | |
2518 | |
2074 /* Debugging function to print out the contents of a bitmap. */ | 2519 /* Debugging function to print out the contents of a bitmap. */ |
2075 | 2520 |
2076 DEBUG_FUNCTION void | 2521 DEBUG_FUNCTION void |
2077 debug_bitmap_file (FILE *file, const_bitmap head) | 2522 debug_bitmap_file (FILE *file, const_bitmap head) |
2078 { | 2523 { |
2080 | 2525 |
2081 fprintf (file, "\nfirst = " HOST_PTR_PRINTF | 2526 fprintf (file, "\nfirst = " HOST_PTR_PRINTF |
2082 " current = " HOST_PTR_PRINTF " indx = %u\n", | 2527 " current = " HOST_PTR_PRINTF " indx = %u\n", |
2083 (void *) head->first, (void *) head->current, head->indx); | 2528 (void *) head->first, (void *) head->current, head->indx); |
2084 | 2529 |
2085 for (ptr = head->first; ptr; ptr = ptr->next) | 2530 if (head->tree_form) |
2086 { | 2531 { |
2087 unsigned int i, j, col = 26; | 2532 auto_vec<bitmap_element *, 32> elts; |
2088 | 2533 bitmap_tree_to_vec (elts, head); |
2089 fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF | 2534 for (unsigned i = 0; i < elts.length (); ++i) |
2090 " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {", | 2535 debug_bitmap_elt_file (file, elts[i]); |
2091 (const void*) ptr, (const void*) ptr->next, | 2536 } |
2092 (const void*) ptr->prev, ptr->indx); | 2537 else |
2093 | 2538 for (ptr = head->first; ptr; ptr = ptr->next) |
2094 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | 2539 debug_bitmap_elt_file (file, ptr); |
2095 for (j = 0; j < BITMAP_WORD_BITS; j++) | |
2096 if ((ptr->bits[i] >> j) & 1) | |
2097 { | |
2098 if (col > 70) | |
2099 { | |
2100 fprintf (file, "\n\t\t\t"); | |
2101 col = 24; | |
2102 } | |
2103 | |
2104 fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS | |
2105 + i * BITMAP_WORD_BITS + j)); | |
2106 col += 4; | |
2107 } | |
2108 | |
2109 fprintf (file, " }\n"); | |
2110 } | |
2111 } | 2540 } |
2112 | 2541 |
2113 /* Function to be called from the debugger to print the contents | 2542 /* Function to be called from the debugger to print the contents |
2114 of a bitmap. */ | 2543 of a bitmap. */ |
2115 | 2544 |
2126 bitmap_print (FILE *file, const_bitmap head, const char *prefix, | 2555 bitmap_print (FILE *file, const_bitmap head, const char *prefix, |
2127 const char *suffix) | 2556 const char *suffix) |
2128 { | 2557 { |
2129 const char *comma = ""; | 2558 const char *comma = ""; |
2130 unsigned i; | 2559 unsigned i; |
2131 bitmap_iterator bi; | |
2132 | 2560 |
2133 fputs (prefix, file); | 2561 fputs (prefix, file); |
2134 EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi) | 2562 if (head->tree_form) |
2135 { | 2563 { |
2136 fprintf (file, "%s%d", comma, i); | 2564 auto_vec<bitmap_element *, 32> elts; |
2137 comma = ", "; | 2565 bitmap_tree_to_vec (elts, head); |
2566 for (i = 0; i < elts.length (); ++i) | |
2567 for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ++ix) | |
2568 { | |
2569 BITMAP_WORD word = elts[i]->bits[ix]; | |
2570 for (unsigned bit = 0; bit != BITMAP_WORD_BITS; ++bit) | |
2571 if (word & ((BITMAP_WORD)1 << bit)) | |
2572 { | |
2573 fprintf (file, "%s%d", comma, | |
2574 (bit + BITMAP_WORD_BITS * ix | |
2575 + elts[i]->indx * BITMAP_ELEMENT_ALL_BITS)); | |
2576 comma = ", "; | |
2577 } | |
2578 } | |
2579 } | |
2580 else | |
2581 { | |
2582 bitmap_iterator bi; | |
2583 EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi) | |
2584 { | |
2585 fprintf (file, "%s%d", comma, i); | |
2586 comma = ", "; | |
2587 } | |
2138 } | 2588 } |
2139 fputs (suffix, file); | 2589 fputs (suffix, file); |
2140 } | 2590 } |
2141 | 2591 |
2142 /* Output per-bitmap memory usage statistics. */ | 2592 /* Output per-bitmap memory usage statistics. */ |
2160 { | 2610 { |
2161 if (ptr) | 2611 if (ptr) |
2162 debug (*ptr); | 2612 debug (*ptr); |
2163 else | 2613 else |
2164 fprintf (stderr, "<nil>\n"); | 2614 fprintf (stderr, "<nil>\n"); |
2615 } | |
2616 | |
2617 void | |
2618 bitmap_head::dump () | |
2619 { | |
2620 debug (this); | |
2165 } | 2621 } |
2166 | 2622 |
2167 #if CHECKING_P | 2623 #if CHECKING_P |
2168 | 2624 |
2169 namespace selftest { | 2625 namespace selftest { |