]>
Commit | Line | Data |
---|---|---|
5f6c11d6 | 1 | /* Simple bitmaps. |
818ab71a | 2 | Copyright (C) 1999-2016 Free Software Foundation, Inc. |
5f6c11d6 | 3 | |
1322177d | 4 | This file is part of GCC. |
5f6c11d6 | 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. |
5f6c11d6 | 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. | |
5f6c11d6 RH |
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/>. */ | |
5f6c11d6 | 19 | |
88657302 | 20 | #ifndef GCC_SBITMAP_H |
46c5ad27 | 21 | #define GCC_SBITMAP_H |
4dc9341c | 22 | |
0263463d SB |
23 | /* Implementation of sets using simple bitmap vectors. |
24 | ||
25 | This set representation is suitable for non-sparse sets with a known | |
26 | (a priori) universe. The set is represented as a simple array of the | |
27 | host's fastest unsigned integer. For a given member I in the set: | |
28 | - the element for I will be at sbitmap[I / (bits per element)] | |
29 | - the position for I within element is I % (bits per element) | |
30 | ||
31 | This representation is very space-efficient for large non-sparse sets | |
32 | with random access patterns. | |
33 | ||
34 | The following operations can be performed in O(1) time: | |
35 | ||
36 | * set_size : SBITMAP_SIZE | |
d7c028c0 LC |
37 | * member_p : bitmap_bit_p |
38 | * add_member : bitmap_set_bit | |
39 | * remove_member : bitmap_clear_bit | |
0263463d SB |
40 | |
41 | Most other operations on this set representation are O(U) where U is | |
42 | the size of the set universe: | |
43 | ||
f61e445a | 44 | * clear : bitmap_clear |
f61e445a LC |
45 | * choose_one : bitmap_first_set_bit / |
46 | bitmap_last_set_bit | |
d4ac4ce2 | 47 | * forall : EXECUTE_IF_SET_IN_BITMAP |
5fd39ce6 | 48 | * set_copy : bitmap_copy |
f61e445a LC |
49 | * set_intersection : bitmap_and |
50 | * set_union : bitmap_ior | |
51 | * set_difference : bitmap_and_compl | |
0263463d | 52 | * set_disjuction : (not implemented) |
f61e445a | 53 | * set_compare : bitmap_equal_p |
0263463d | 54 | |
026c3cfd | 55 | Some operations on 3 sets that occur frequently in data flow problems |
0263463d SB |
56 | are also implemented: |
57 | ||
f61e445a LC |
58 | * A | (B & C) : bitmap_or_and |
59 | * A | (B & ~C) : bitmap_ior_and_compl | |
60 | * A & (B | C) : bitmap_and_or | |
0263463d SB |
61 | |
62 | Most of the set functions have two variants: One that returns non-zero | |
63 | if members were added or removed from the target set, and one that just | |
64 | performs the operation without feedback. The former operations are a | |
65 | bit more expensive but the result can often be used to avoid iterations | |
66 | on other sets. | |
67 | ||
68 | Allocating a bitmap is done with sbitmap_alloc, and resizing is | |
69 | performed with sbitmap_resize. | |
70 | ||
71 | The storage requirements for simple bitmap sets is O(U) where U is the | |
72 | size of the set universe (colloquially the number of bits in the bitmap). | |
73 | ||
74 | This set representation works well for relatively small data flow problems | |
75 | (there are special routines for that, see sbitmap_vector_*). The set | |
76 | operations can be vectorized and there is almost no computating overhead, | |
77 | so that even sparse simple bitmap sets outperform dedicated sparse set | |
78 | representations like linked-list bitmaps. For larger problems, the size | |
79 | overhead of simple bitmap sets gets too high and other set representations | |
80 | have to be used. */ | |
5f6c11d6 | 81 | |
7aa6d18a | 82 | #define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u) |
99fa8911 | 83 | #define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT |
5f6c11d6 | 84 | |
7a8cba34 | 85 | struct simple_bitmap_def |
08158df3 | 86 | { |
97508a6b | 87 | unsigned char *popcount; /* Population count. */ |
08158df3 RK |
88 | unsigned int n_bits; /* Number of bits. */ |
89 | unsigned int size; /* Size in elements. */ | |
08158df3 | 90 | SBITMAP_ELT_TYPE elms[1]; /* The elements. */ |
7a8cba34 | 91 | }; |
5f6c11d6 | 92 | |
5f6c11d6 | 93 | /* Return the set size needed for N elements. */ |
08158df3 | 94 | #define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS) |
5f6c11d6 | 95 | |
0263463d SB |
96 | /* Return the number of bits in BITMAP. */ |
97 | #define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits) | |
98 | ||
08158df3 | 99 | /* Test if bit number bitno in the bitmap is set. */ |
0263463d | 100 | static inline SBITMAP_ELT_TYPE |
d7c028c0 | 101 | bitmap_bit_p (const_sbitmap map, int bitno) |
0263463d SB |
102 | { |
103 | size_t i = bitno / SBITMAP_ELT_BITS; | |
104 | unsigned int s = bitno % SBITMAP_ELT_BITS; | |
105 | return (map->elms[i] >> s) & (SBITMAP_ELT_TYPE) 1; | |
106 | } | |
5f6c11d6 | 107 | |
0263463d | 108 | /* Set bit number BITNO in the sbitmap MAP. */ |
97508a6b DB |
109 | |
110 | static inline void | |
d7c028c0 | 111 | bitmap_set_bit (sbitmap map, int bitno) |
97508a6b | 112 | { |
0263463d | 113 | gcc_checking_assert (! map->popcount); |
97508a6b DB |
114 | map->elms[bitno / SBITMAP_ELT_BITS] |
115 | |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS; | |
116 | } | |
117 | ||
0263463d | 118 | /* Reset bit number BITNO in the sbitmap MAP. */ |
97508a6b DB |
119 | |
120 | static inline void | |
d7c028c0 | 121 | bitmap_clear_bit (sbitmap map, int bitno) |
97508a6b | 122 | { |
0263463d SB |
123 | gcc_checking_assert (! map->popcount); |
124 | map->elms[bitno / SBITMAP_ELT_BITS] | |
125 | &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS); | |
126 | } | |
127 | ||
b6e7e9af | 128 | /* The iterator for sbitmap. */ |
84562394 | 129 | struct sbitmap_iterator { |
b6e7e9af | 130 | /* The pointer to the first word of the bitmap. */ |
be5b01f3 | 131 | const SBITMAP_ELT_TYPE *ptr; |
b6e7e9af KH |
132 | |
133 | /* The size of the bitmap. */ | |
134 | unsigned int size; | |
135 | ||
136 | /* The current word index. */ | |
137 | unsigned int word_num; | |
138 | ||
108267cd | 139 | /* The current bit index (not modulo SBITMAP_ELT_BITS). */ |
b6e7e9af KH |
140 | unsigned int bit_num; |
141 | ||
142 | /* The words currently visited. */ | |
143 | SBITMAP_ELT_TYPE word; | |
84562394 | 144 | }; |
b6e7e9af KH |
145 | |
146 | /* Initialize the iterator I with sbitmap BMP and the initial index | |
147 | MIN. */ | |
148 | ||
149 | static inline void | |
d4ac4ce2 LC |
150 | bmp_iter_set_init (sbitmap_iterator *i, const_sbitmap bmp, |
151 | unsigned int min, unsigned *bit_no ATTRIBUTE_UNUSED) | |
b6e7e9af KH |
152 | { |
153 | i->word_num = min / (unsigned int) SBITMAP_ELT_BITS; | |
108267cd | 154 | i->bit_num = min; |
b6e7e9af KH |
155 | i->size = bmp->size; |
156 | i->ptr = bmp->elms; | |
157 | ||
158 | if (i->word_num >= i->size) | |
159 | i->word = 0; | |
160 | else | |
108267cd KH |
161 | i->word = (i->ptr[i->word_num] |
162 | >> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS)); | |
b6e7e9af KH |
163 | } |
164 | ||
165 | /* Return true if we have more bits to visit, in which case *N is set | |
166 | to the index of the bit to be visited. Otherwise, return | |
167 | false. */ | |
168 | ||
169 | static inline bool | |
d4ac4ce2 | 170 | bmp_iter_set (sbitmap_iterator *i, unsigned int *n) |
b6e7e9af KH |
171 | { |
172 | /* Skip words that are zeros. */ | |
173 | for (; i->word == 0; i->word = i->ptr[i->word_num]) | |
174 | { | |
175 | i->word_num++; | |
176 | ||
177 | /* If we have reached the end, break. */ | |
178 | if (i->word_num >= i->size) | |
179 | return false; | |
180 | ||
181 | i->bit_num = i->word_num * SBITMAP_ELT_BITS; | |
182 | } | |
183 | ||
184 | /* Skip bits that are zero. */ | |
185 | for (; (i->word & 1) == 0; i->word >>= 1) | |
186 | i->bit_num++; | |
187 | ||
188 | *n = i->bit_num; | |
189 | ||
190 | return true; | |
191 | } | |
192 | ||
193 | /* Advance to the next bit. */ | |
194 | ||
195 | static inline void | |
d4ac4ce2 | 196 | bmp_iter_next (sbitmap_iterator *i, unsigned *bit_no ATTRIBUTE_UNUSED) |
b6e7e9af KH |
197 | { |
198 | i->word >>= 1; | |
199 | i->bit_num++; | |
200 | } | |
201 | ||
202 | /* Loop over all elements of SBITMAP, starting with MIN. In each | |
203 | iteration, N is set to the index of the bit being visited. ITER is | |
204 | an instance of sbitmap_iterator used to iterate the bitmap. */ | |
205 | ||
d4ac4ce2 LC |
206 | #ifndef EXECUTE_IF_SET_IN_BITMAP |
207 | /* See bitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */ | |
208 | #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \ | |
209 | for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \ | |
210 | bmp_iter_set (&(ITER), &(BITNUM)); \ | |
211 | bmp_iter_next (&(ITER), &(BITNUM))) | |
212 | #endif | |
ed8d2920 | 213 | |
f61e445a LC |
214 | inline void sbitmap_free (sbitmap map) |
215 | { | |
216 | free (map->popcount); | |
217 | free (map); | |
218 | } | |
5f6c11d6 | 219 | |
f61e445a LC |
220 | inline void sbitmap_vector_free (sbitmap * vec) |
221 | { | |
222 | free (vec); | |
223 | } | |
224 | ||
225 | extern void dump_bitmap (FILE *, const_sbitmap); | |
7b3b6ae4 LC |
226 | extern void debug_raw (const simple_bitmap_def &ref); |
227 | extern void debug_raw (const simple_bitmap_def *ptr); | |
f61e445a | 228 | extern void dump_bitmap_file (FILE *, const_sbitmap); |
7b3b6ae4 LC |
229 | extern void debug (const simple_bitmap_def &ref); |
230 | extern void debug (const simple_bitmap_def *ptr); | |
f61e445a | 231 | extern void dump_bitmap_vector (FILE *, const char *, const char *, sbitmap *, |
46c5ad27 AJ |
232 | int); |
233 | extern sbitmap sbitmap_alloc (unsigned int); | |
97508a6b | 234 | extern sbitmap sbitmap_alloc_with_popcount (unsigned int); |
46c5ad27 AJ |
235 | extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int); |
236 | extern sbitmap sbitmap_resize (sbitmap, unsigned int, int); | |
f61e445a | 237 | extern void bitmap_copy (sbitmap, const_sbitmap); |
f61e445a LC |
238 | extern int bitmap_equal_p (const_sbitmap, const_sbitmap); |
239 | extern bool bitmap_empty_p (const_sbitmap); | |
f61e445a LC |
240 | extern void bitmap_clear (sbitmap); |
241 | extern void bitmap_ones (sbitmap); | |
242 | extern void bitmap_vector_clear (sbitmap *, unsigned int); | |
243 | extern void bitmap_vector_ones (sbitmap *, unsigned int); | |
244 | ||
245 | extern bool bitmap_ior_and_compl (sbitmap, const_sbitmap, | |
0263463d | 246 | const_sbitmap, const_sbitmap); |
f61e445a LC |
247 | extern void bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap); |
248 | extern void bitmap_not (sbitmap, const_sbitmap); | |
249 | extern bool bitmap_or_and (sbitmap, const_sbitmap, | |
0263463d | 250 | const_sbitmap, const_sbitmap); |
f61e445a | 251 | extern bool bitmap_and_or (sbitmap, const_sbitmap, |
0263463d | 252 | const_sbitmap, const_sbitmap); |
f61e445a LC |
253 | extern bool bitmap_intersect_p (const_sbitmap, const_sbitmap); |
254 | extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap); | |
255 | extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap); | |
256 | extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap); | |
257 | extern bool bitmap_subset_p (const_sbitmap, const_sbitmap); | |
258 | ||
259 | extern int bitmap_first_set_bit (const_sbitmap); | |
260 | extern int bitmap_last_set_bit (const_sbitmap); | |
261 | ||
262 | extern void debug_bitmap (const_sbitmap); | |
6de9cd9a | 263 | extern sbitmap sbitmap_realloc (sbitmap, unsigned int); |
3c2c4f22 | 264 | extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long); |
88657302 | 265 | #endif /* ! GCC_SBITMAP_H */ |