Mercurial > hg > CbC > CbC_gcc
comparison gcc/bitmap.h @ 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 |
18 <http://www.gnu.org/licenses/>. */ | 18 <http://www.gnu.org/licenses/>. */ |
19 | 19 |
20 #ifndef GCC_BITMAP_H | 20 #ifndef GCC_BITMAP_H |
21 #define GCC_BITMAP_H | 21 #define GCC_BITMAP_H |
22 | 22 |
23 /* Implementation of sparse integer sets as a linked list. | 23 /* Implementation of sparse integer sets as a linked list or tree. |
24 | 24 |
25 This sparse set representation is suitable for sparse sets with an | 25 This sparse set representation is suitable for sparse sets with an |
26 unknown (a priori) universe. The set is represented as a double-linked | 26 unknown (a priori) universe. |
27 list of container nodes (struct bitmap_element). Each node consists | 27 |
28 of an index for the first member that could be held in the container, | 28 Sets are represented as double-linked lists of container nodes of |
29 a small array of integers that represent the members in the container, | 29 type "struct bitmap_element" or as a binary trees of the same |
30 and pointers to the next and previous element in the linked list. The | 30 container nodes. Each container node consists of an index for the |
31 elements in the list are sorted in ascending order, i.e. the head of | 31 first member that could be held in the container, a small array of |
32 integers that represent the members in the container, and pointers | |
33 to the next and previous element in the linked list, or left and | |
34 right children in the tree. In linked-list form, the container | |
35 nodes in the list are sorted in ascending order, i.e. the head of | |
32 the list holds the element with the smallest member of the set. | 36 the list holds the element with the smallest member of the set. |
37 In tree form, nodes to the left have a smaller container index. | |
33 | 38 |
34 For a given member I in the set: | 39 For a given member I in the set: |
35 - the element for I will have index is I / (bits per element) | 40 - the element for I will have index is I / (bits per element) |
36 - the position for I within element is I % (bits per element) | 41 - the position for I within element is I % (bits per element) |
37 | 42 |
40 An important parameter is the number of bits per element. In this | 45 An important parameter is the number of bits per element. In this |
41 implementation, there are 128 bits per element. This results in a | 46 implementation, there are 128 bits per element. This results in a |
42 high storage overhead *per element*, but a small overall overhead if | 47 high storage overhead *per element*, but a small overall overhead if |
43 the set is very sparse. | 48 the set is very sparse. |
44 | 49 |
45 The downside is that many operations are relatively slow because the | 50 The storage requirements for linked-list sparse sets are O(E), with E->N |
46 linked list has to be traversed to test membership (i.e. member_p/ | 51 in the worst case (a sparse set with large distances between the values |
47 add_member/remove_member). To improve the performance of this set | 52 of the set members). |
48 representation, the last accessed element and its index are cached. | 53 |
49 For membership tests on members close to recently accessed members, | 54 This representation also works well for data flow problems where the size |
50 the cached last element improves membership test to a constant-time | 55 of the set may grow dynamically, but care must be taken that the member_p, |
51 operation. | 56 add_member, and remove_member operations occur with a suitable access |
52 | 57 pattern. |
53 The following operations can always be performed in O(1) time: | 58 |
59 The linked-list set representation works well for problems involving very | |
60 sparse sets. The canonical example in GCC is, of course, the "set of | |
61 sets" for some CFG-based data flow problems (liveness analysis, dominance | |
62 frontiers, etc.). | |
63 | |
64 For random-access sparse sets of unknown universe, the binary tree | |
65 representation is likely to be a more suitable choice. Theoretical | |
66 access times for the binary tree representation are better than those | |
67 for the linked-list, but in practice this is only true for truely | |
68 random access. | |
69 | |
70 Often the most suitable representation during construction of the set | |
71 is not the best choice for the usage of the set. For such cases, the | |
72 "view" of the set can be changed from one representation to the other. | |
73 This is an O(E) operation: | |
74 | |
75 * from list to tree view : bitmap_tree_view | |
76 * from tree to list view : bitmap_list_view | |
77 | |
78 Traversing linked lists or trees can be cache-unfriendly. Performance | |
79 can be improved by keeping container nodes in the set grouped together | |
80 in memory, using a dedicated obstack for a set (or group of related | |
81 sets). Elements allocated on obstacks are released to a free-list and | |
82 taken off the free list. If multiple sets are allocated on the same | |
83 obstack, elements freed from one set may be re-used for one of the other | |
84 sets. This usually helps avoid cache misses. | |
85 | |
86 A single free-list is used for all sets allocated in GGC space. This is | |
87 bad for persistent sets, so persistent sets should be allocated on an | |
88 obstack whenever possible. | |
89 | |
90 For random-access sets with a known, relatively small universe size, the | |
91 SparseSet or simple bitmap representations may be more efficient than a | |
92 linked-list set. | |
93 | |
94 | |
95 LINKED LIST FORM | |
96 ================ | |
97 | |
98 In linked-list form, in-order iterations of the set can be executed | |
99 efficiently. The downside is that many random-access operations are | |
100 relatively slow, because the linked list has to be traversed to test | |
101 membership (i.e. member_p/ add_member/remove_member). | |
102 | |
103 To improve the performance of this set representation, the last | |
104 accessed element and its index are cached. For membership tests on | |
105 members close to recently accessed members, the cached last element | |
106 improves membership test to a constant-time operation. | |
107 | |
108 The following operations can always be performed in O(1) time in | |
109 list view: | |
54 | 110 |
55 * clear : bitmap_clear | 111 * clear : bitmap_clear |
112 * smallest_member : bitmap_first_set_bit | |
56 * choose_one : (not implemented, but could be | 113 * choose_one : (not implemented, but could be |
57 implemented in constant time) | 114 in constant time) |
58 | 115 |
59 The following operations can be performed in O(E) time worst-case (with | 116 The following operations can be performed in O(E) time worst-case in |
60 E the number of elements in the linked list), but in O(1) time with a | 117 list view (with E the number of elements in the linked list), but in |
61 suitable access patterns: | 118 O(1) time with a suitable access patterns: |
62 | 119 |
63 * member_p : bitmap_bit_p | 120 * member_p : bitmap_bit_p |
64 * add_member : bitmap_set_bit | 121 * add_member : bitmap_set_bit / bitmap_set_range |
65 * remove_member : bitmap_clear_bit | 122 * remove_member : bitmap_clear_bit / bitmap_clear_range |
66 | 123 |
67 The following operations can be performed in O(E) time: | 124 The following operations can be performed in O(E) time in list view: |
68 | 125 |
69 * cardinality : bitmap_count_bits | 126 * cardinality : bitmap_count_bits |
70 * set_size : bitmap_last_set_bit (but this could | 127 * largest_member : bitmap_last_set_bit (but this could |
71 in constant time with a pointer to | 128 in constant time with a pointer to |
72 the last element in the chain) | 129 the last element in the chain) |
130 * set_size : bitmap_last_set_bit | |
131 | |
132 In tree view the following operations can all be performed in O(log E) | |
133 amortized time with O(E) worst-case behavior. | |
134 | |
135 * smallest_member | |
136 * largest_member | |
137 * set_size | |
138 * member_p | |
139 * add_member | |
140 * remove_member | |
73 | 141 |
74 Additionally, the linked-list sparse set representation supports | 142 Additionally, the linked-list sparse set representation supports |
75 enumeration of the members in O(E) time: | 143 enumeration of the members in O(E) time: |
76 | 144 |
77 * forall : EXECUTE_IF_SET_IN_BITMAP | 145 * forall : EXECUTE_IF_SET_IN_BITMAP |
91 | 159 |
92 * A | (B & C) : bitmap_ior_and_into | 160 * A | (B & C) : bitmap_ior_and_into |
93 * A | (B & ~C) : bitmap_ior_and_compl / | 161 * A | (B & ~C) : bitmap_ior_and_compl / |
94 bitmap_ior_and_compl_into | 162 bitmap_ior_and_compl_into |
95 | 163 |
96 The storage requirements for linked-list sparse sets are O(E), with E->N | 164 |
97 in the worst case (a sparse set with large distances between the values | 165 BINARY TREE FORM |
98 of the set members). | 166 ================ |
99 | 167 An alternate "view" of a bitmap is its binary tree representation. |
100 The linked-list set representation works well for problems involving very | 168 For this representation, splay trees are used because they can be |
101 sparse sets. The canonical example in GCC is, of course, the "set of | 169 implemented using the same data structures as the linked list, with |
102 sets" for some CFG-based data flow problems (liveness analysis, dominance | 170 no overhead for meta-data (like color, or rank) on the tree nodes. |
103 frontiers, etc.). | 171 |
172 In binary tree form, random-access to the set is much more efficient | |
173 than for the linked-list representation. Downsides are the high cost | |
174 of clearing the set, and the relatively large number of operations | |
175 necessary to balance the tree. Also, iterating the set members is | |
176 not supported. | |
104 | 177 |
105 This representation also works well for data flow problems where the size | 178 As for the linked-list representation, the last accessed element and |
106 of the set may grow dynamically, but care must be taken that the member_p, | 179 its index are cached, so that membership tests on the latest accessed |
107 add_member, and remove_member operations occur with a suitable access | 180 members is a constant-time operation. Other lookups take O(logE) |
108 pattern. | 181 time amortized (but O(E) time worst-case). |
109 | 182 |
110 For random-access sets with a known, relatively small universe size, the | 183 The following operations can always be performed in O(1) time: |
111 SparseSet or simple bitmap representations may be more efficient than a | 184 |
112 linked-list set. For random-access sets of unknown universe, a hash table | 185 * choose_one : (not implemented, but could be |
113 or a balanced binary tree representation is likely to be a more suitable | 186 implemented in constant time) |
114 choice. | 187 |
115 | 188 The following operations can be performed in O(logE) time amortized |
116 Traversing linked lists is usually cache-unfriendly, even with the last | 189 but O(E) time worst-case, but in O(1) time if the same element is |
117 accessed element cached. | 190 accessed. |
118 | 191 |
119 Cache performance can be improved by keeping the elements in the set | 192 * member_p : bitmap_bit_p |
120 grouped together in memory, using a dedicated obstack for a set (or group | 193 * add_member : bitmap_set_bit |
121 of related sets). Elements allocated on obstacks are released to a | 194 * remove_member : bitmap_clear_bit |
122 free-list and taken off the free list. If multiple sets are allocated on | 195 |
123 the same obstack, elements freed from one set may be re-used for one of | 196 The following operations can be performed in O(logE) time amortized |
124 the other sets. This usually helps avoid cache misses. | 197 but O(E) time worst-case: |
125 | 198 |
126 A single free-list is used for all sets allocated in GGC space. This is | 199 * smallest_member : bitmap_first_set_bit |
127 bad for persistent sets, so persistent sets should be allocated on an | 200 * largest_member : bitmap_last_set_bit |
128 obstack whenever possible. */ | 201 * set_size : bitmap_last_set_bit |
202 | |
203 The following operations can be performed in O(E) time: | |
204 | |
205 * clear : bitmap_clear | |
206 | |
207 The binary tree sparse set representation does *not* support any form | |
208 of enumeration, and does also *not* support logical operations on sets. | |
209 The binary tree representation is only supposed to be used for sets | |
210 on which many random-access membership tests will happen. */ | |
129 | 211 |
130 #include "obstack.h" | 212 #include "obstack.h" |
131 | 213 |
132 /* Bitmap memory usage. */ | 214 /* Bitmap memory usage. */ |
133 struct bitmap_usage: public mem_usage | 215 struct bitmap_usage: public mem_usage |
223 is undefined for interior elements. This allows | 305 is undefined for interior elements. This allows |
224 bitmap_elt_clear_from to be implemented in unit time rather than | 306 bitmap_elt_clear_from to be implemented in unit time rather than |
225 linear in the number of elements to be freed. */ | 307 linear in the number of elements to be freed. */ |
226 | 308 |
227 struct GTY((chain_next ("%h.next"), chain_prev ("%h.prev"))) bitmap_element { | 309 struct GTY((chain_next ("%h.next"), chain_prev ("%h.prev"))) bitmap_element { |
228 struct bitmap_element *next; /* Next element. */ | 310 /* In list form, the next element in the linked list; |
229 struct bitmap_element *prev; /* Previous element. */ | 311 in tree form, the left child node in the tree. */ |
230 unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */ | 312 struct bitmap_element *next; |
231 BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */ | 313 /* In list form, the previous element in the linked list; |
314 in tree form, the right child node in the tree. */ | |
315 struct bitmap_element *prev; | |
316 /* regno/BITMAP_ELEMENT_ALL_BITS. */ | |
317 unsigned int indx; | |
318 /* Bits that are set, counting from INDX, inclusive */ | |
319 BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; | |
232 }; | 320 }; |
233 | 321 |
234 /* Head of bitmap linked list. The 'current' member points to something | 322 /* Head of bitmap linked list. The 'current' member points to something |
235 already pointed to by the chain started by first, so GTY((skip)) it. */ | 323 already pointed to by the chain started by first, so GTY((skip)) it. */ |
236 | 324 |
237 struct GTY(()) bitmap_head { | 325 struct GTY(()) bitmap_head { |
238 unsigned int indx; /* Index of last element looked at. */ | 326 /* Index of last element looked at. */ |
239 unsigned int descriptor_id; /* Unique identifier for the allocation | 327 unsigned int indx; |
240 site of this bitmap, for detailed | 328 /* False if the bitmap is in list form; true if the bitmap is in tree form. |
241 statistics gathering. */ | 329 Bitmap iterators only work on bitmaps in list form. */ |
242 bitmap_element *first; /* First element in linked list. */ | 330 bool tree_form; |
243 bitmap_element * GTY((skip(""))) current; /* Last element looked at. */ | 331 /* In list form, the first element in the linked list; |
244 bitmap_obstack *obstack; /* Obstack to allocate elements from. | 332 in tree form, the root of the tree. */ |
245 If NULL, then use GGC allocation. */ | 333 bitmap_element *first; |
334 /* Last element looked at. */ | |
335 bitmap_element * GTY((skip(""))) current; | |
336 /* Obstack to allocate elements from. If NULL, then use GGC allocation. */ | |
337 bitmap_obstack *obstack; | |
338 void dump (); | |
246 }; | 339 }; |
247 | 340 |
248 /* Global data */ | 341 /* Global data */ |
249 extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ | 342 extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ |
250 extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */ | 343 extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */ |
344 | |
345 /* Change the view of the bitmap to list, or tree. */ | |
346 void bitmap_list_view (bitmap); | |
347 void bitmap_tree_view (bitmap); | |
251 | 348 |
252 /* Clear a bitmap by freeing up the linked list. */ | 349 /* Clear a bitmap by freeing up the linked list. */ |
253 extern void bitmap_clear (bitmap); | 350 extern void bitmap_clear (bitmap); |
254 | 351 |
255 /* Copy a bitmap to another bitmap. */ | 352 /* Copy a bitmap to another bitmap. */ |
313 extern bool bitmap_clear_bit (bitmap, int); | 410 extern bool bitmap_clear_bit (bitmap, int); |
314 | 411 |
315 /* Set a single bit in a bitmap. Return true if the bit changed. */ | 412 /* Set a single bit in a bitmap. Return true if the bit changed. */ |
316 extern bool bitmap_set_bit (bitmap, int); | 413 extern bool bitmap_set_bit (bitmap, int); |
317 | 414 |
318 /* Return true if a register is set in a register set. */ | 415 /* Return true if a bit is set in a bitmap. */ |
319 extern int bitmap_bit_p (bitmap, int); | 416 extern int bitmap_bit_p (bitmap, int); |
320 | 417 |
321 /* Debug functions to print a bitmap linked list. */ | 418 /* Debug functions to print a bitmap. */ |
322 extern void debug_bitmap (const_bitmap); | 419 extern void debug_bitmap (const_bitmap); |
323 extern void debug_bitmap_file (FILE *, const_bitmap); | 420 extern void debug_bitmap_file (FILE *, const_bitmap); |
324 | 421 |
325 /* Print a bitmap. */ | 422 /* Print a bitmap. */ |
326 extern void bitmap_print (FILE *, const_bitmap, const char *, const char *); | 423 extern void bitmap_print (FILE *, const_bitmap, const char *, const char *); |
336 | 433 |
337 static inline void | 434 static inline void |
338 bitmap_initialize (bitmap head, bitmap_obstack *obstack CXX_MEM_STAT_INFO) | 435 bitmap_initialize (bitmap head, bitmap_obstack *obstack CXX_MEM_STAT_INFO) |
339 { | 436 { |
340 head->first = head->current = NULL; | 437 head->first = head->current = NULL; |
438 head->indx = head->tree_form = 0; | |
341 head->obstack = obstack; | 439 head->obstack = obstack; |
342 if (GATHER_STATISTICS) | 440 if (GATHER_STATISTICS) |
343 bitmap_register (head PASS_MEM_STAT); | 441 bitmap_register (head PASS_MEM_STAT); |
344 } | 442 } |
345 | 443 |
395 unsigned start_bit, unsigned *bit_no) | 493 unsigned start_bit, unsigned *bit_no) |
396 { | 494 { |
397 bi->elt1 = map->first; | 495 bi->elt1 = map->first; |
398 bi->elt2 = NULL; | 496 bi->elt2 = NULL; |
399 | 497 |
498 gcc_checking_assert (!map->tree_form); | |
499 | |
400 /* Advance elt1 until it is not before the block containing start_bit. */ | 500 /* Advance elt1 until it is not before the block containing start_bit. */ |
401 while (1) | 501 while (1) |
402 { | 502 { |
403 if (!bi->elt1) | 503 if (!bi->elt1) |
404 { | 504 { |
437 unsigned start_bit, unsigned *bit_no) | 537 unsigned start_bit, unsigned *bit_no) |
438 { | 538 { |
439 bi->elt1 = map1->first; | 539 bi->elt1 = map1->first; |
440 bi->elt2 = map2->first; | 540 bi->elt2 = map2->first; |
441 | 541 |
542 gcc_checking_assert (!map1->tree_form && !map2->tree_form); | |
543 | |
442 /* Advance elt1 until it is not before the block containing | 544 /* Advance elt1 until it is not before the block containing |
443 start_bit. */ | 545 start_bit. */ |
444 while (1) | 546 while (1) |
445 { | 547 { |
446 if (!bi->elt1) | 548 if (!bi->elt1) |
495 start_bit += !bi->bits; | 597 start_bit += !bi->bits; |
496 | 598 |
497 *bit_no = start_bit; | 599 *bit_no = start_bit; |
498 } | 600 } |
499 | 601 |
500 /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2. | 602 /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2. */ |
501 */ | |
502 | 603 |
503 static inline void | 604 static inline void |
504 bmp_iter_and_compl_init (bitmap_iterator *bi, | 605 bmp_iter_and_compl_init (bitmap_iterator *bi, |
505 const_bitmap map1, const_bitmap map2, | 606 const_bitmap map1, const_bitmap map2, |
506 unsigned start_bit, unsigned *bit_no) | 607 unsigned start_bit, unsigned *bit_no) |
507 { | 608 { |
508 bi->elt1 = map1->first; | 609 bi->elt1 = map1->first; |
509 bi->elt2 = map2->first; | 610 bi->elt2 = map2->first; |
611 | |
612 gcc_checking_assert (!map1->tree_form && !map2->tree_form); | |
510 | 613 |
511 /* Advance elt1 until it is not before the block containing start_bit. */ | 614 /* Advance elt1 until it is not before the block containing start_bit. */ |
512 while (1) | 615 while (1) |
513 { | 616 { |
514 if (!bi->elt1) | 617 if (!bi->elt1) |