Mercurial > hg > CbC > CbC_gcc
annotate gcc/sbitmap.h @ 120:f93fa5091070
fix conv1.c
author | mir3636 |
---|---|
date | Thu, 08 Mar 2018 14:53:42 +0900 |
parents | 04ced10e8804 |
children | 84e7813d76e9 |
rev | line source |
---|---|
0 | 1 /* Simple bitmaps. |
111 | 2 Copyright (C) 1999-2017 Free Software Foundation, Inc. |
0 | 3 |
4 This file is part of GCC. | |
5 | |
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 | |
8 Software Foundation; either version 3, or (at your option) any later | |
9 version. | |
10 | |
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. | |
15 | |
16 You should have received a copy of the GNU General Public License | |
17 along with GCC; see the file COPYING3. If not see | |
18 <http://www.gnu.org/licenses/>. */ | |
19 | |
20 #ifndef GCC_SBITMAP_H | |
21 #define GCC_SBITMAP_H | |
22 | |
111 | 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) | |
0 | 30 |
111 | 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 | |
37 * member_p : bitmap_bit_p | |
38 * add_member : bitmap_set_bit | |
39 * remove_member : bitmap_clear_bit | |
40 | |
41 Most other operations on this set representation are O(U) where U is | |
42 the size of the set universe: | |
0 | 43 |
111 | 44 * clear : bitmap_clear |
45 * choose_one : bitmap_first_set_bit / | |
46 bitmap_last_set_bit | |
47 * forall : EXECUTE_IF_SET_IN_BITMAP | |
48 * set_copy : bitmap_copy | |
49 * set_intersection : bitmap_and | |
50 * set_union : bitmap_ior | |
51 * set_difference : bitmap_and_compl | |
52 * set_disjuction : (not implemented) | |
53 * set_compare : bitmap_equal_p | |
54 * bit_in_range_p : bitmap_bit_in_range_p | |
55 | |
56 Some operations on 3 sets that occur frequently in data flow problems | |
57 are also implemented: | |
58 | |
59 * A | (B & C) : bitmap_or_and | |
60 * A | (B & ~C) : bitmap_ior_and_compl | |
61 * A & (B | C) : bitmap_and_or | |
62 | |
63 Most of the set functions have two variants: One that returns non-zero | |
64 if members were added or removed from the target set, and one that just | |
65 performs the operation without feedback. The former operations are a | |
66 bit more expensive but the result can often be used to avoid iterations | |
67 on other sets. | |
68 | |
69 Allocating a bitmap is done with sbitmap_alloc, and resizing is | |
70 performed with sbitmap_resize. | |
71 | |
72 The storage requirements for simple bitmap sets is O(U) where U is the | |
73 size of the set universe (colloquially the number of bits in the bitmap). | |
74 | |
75 This set representation works well for relatively small data flow problems | |
76 (there are special routines for that, see sbitmap_vector_*). The set | |
77 operations can be vectorized and there is almost no computating overhead, | |
78 so that even sparse simple bitmap sets outperform dedicated sparse set | |
79 representations like linked-list bitmaps. For larger problems, the size | |
80 overhead of simple bitmap sets gets too high and other set representations | |
81 have to be used. */ | |
82 | |
83 #define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u) | |
84 #define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT | |
0 | 85 |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
86 struct simple_bitmap_def |
0 | 87 { |
88 unsigned int n_bits; /* Number of bits. */ | |
89 unsigned int size; /* Size in elements. */ | |
90 SBITMAP_ELT_TYPE elms[1]; /* The elements. */ | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
91 }; |
0 | 92 |
93 /* Return the set size needed for N elements. */ | |
94 #define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS) | |
111 | 95 |
96 /* Return the number of bits in BITMAP. */ | |
97 #define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits) | |
98 | |
99 /* Verify that access at INDEX in bitmap MAP is valid. */ | |
0 | 100 |
111 | 101 static inline void |
102 bitmap_check_index (const_sbitmap map, int index) | |
103 { | |
104 gcc_checking_assert (index >= 0); | |
105 gcc_checking_assert ((unsigned int)index < map->n_bits); | |
106 } | |
0 | 107 |
111 | 108 /* Verify that bitmaps A and B have same size. */ |
0 | 109 |
110 static inline void | |
111 | 111 bitmap_check_sizes (const_sbitmap a, const_sbitmap b) |
112 { | |
113 gcc_checking_assert (a->n_bits == b->n_bits); | |
114 } | |
115 | |
116 /* Test if bit number bitno in the bitmap is set. */ | |
117 static inline SBITMAP_ELT_TYPE | |
118 bitmap_bit_p (const_sbitmap map, int bitno) | |
0 | 119 { |
111 | 120 bitmap_check_index (map, bitno); |
121 | |
122 size_t i = bitno / SBITMAP_ELT_BITS; | |
123 unsigned int s = bitno % SBITMAP_ELT_BITS; | |
124 return (map->elms[i] >> s) & (SBITMAP_ELT_TYPE) 1; | |
125 } | |
126 | |
127 /* Set bit number BITNO in the sbitmap MAP. */ | |
128 | |
129 static inline void | |
130 bitmap_set_bit (sbitmap map, int bitno) | |
131 { | |
132 bitmap_check_index (map, bitno); | |
133 | |
0 | 134 map->elms[bitno / SBITMAP_ELT_BITS] |
135 |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS; | |
136 } | |
137 | |
111 | 138 /* Reset bit number BITNO in the sbitmap MAP. */ |
0 | 139 |
140 static inline void | |
111 | 141 bitmap_clear_bit (sbitmap map, int bitno) |
0 | 142 { |
111 | 143 bitmap_check_index (map, bitno); |
144 | |
0 | 145 map->elms[bitno / SBITMAP_ELT_BITS] |
146 &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS); | |
147 } | |
148 | |
149 /* The iterator for sbitmap. */ | |
111 | 150 struct sbitmap_iterator { |
0 | 151 /* The pointer to the first word of the bitmap. */ |
152 const SBITMAP_ELT_TYPE *ptr; | |
153 | |
154 /* The size of the bitmap. */ | |
155 unsigned int size; | |
156 | |
157 /* The current word index. */ | |
158 unsigned int word_num; | |
159 | |
160 /* The current bit index (not modulo SBITMAP_ELT_BITS). */ | |
161 unsigned int bit_num; | |
162 | |
163 /* The words currently visited. */ | |
164 SBITMAP_ELT_TYPE word; | |
111 | 165 }; |
0 | 166 |
167 /* Initialize the iterator I with sbitmap BMP and the initial index | |
168 MIN. */ | |
169 | |
170 static inline void | |
111 | 171 bmp_iter_set_init (sbitmap_iterator *i, const_sbitmap bmp, |
172 unsigned int min, unsigned *bit_no ATTRIBUTE_UNUSED) | |
0 | 173 { |
111 | 174 bitmap_check_index (bmp, min); |
175 | |
0 | 176 i->word_num = min / (unsigned int) SBITMAP_ELT_BITS; |
177 i->bit_num = min; | |
178 i->size = bmp->size; | |
179 i->ptr = bmp->elms; | |
180 | |
181 if (i->word_num >= i->size) | |
182 i->word = 0; | |
183 else | |
184 i->word = (i->ptr[i->word_num] | |
185 >> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS)); | |
186 } | |
187 | |
188 /* Return true if we have more bits to visit, in which case *N is set | |
189 to the index of the bit to be visited. Otherwise, return | |
190 false. */ | |
191 | |
192 static inline bool | |
111 | 193 bmp_iter_set (sbitmap_iterator *i, unsigned int *n) |
0 | 194 { |
195 /* Skip words that are zeros. */ | |
196 for (; i->word == 0; i->word = i->ptr[i->word_num]) | |
197 { | |
198 i->word_num++; | |
199 | |
200 /* If we have reached the end, break. */ | |
201 if (i->word_num >= i->size) | |
202 return false; | |
203 | |
204 i->bit_num = i->word_num * SBITMAP_ELT_BITS; | |
205 } | |
206 | |
207 /* Skip bits that are zero. */ | |
208 for (; (i->word & 1) == 0; i->word >>= 1) | |
209 i->bit_num++; | |
210 | |
211 *n = i->bit_num; | |
212 | |
213 return true; | |
214 } | |
215 | |
216 /* Advance to the next bit. */ | |
217 | |
218 static inline void | |
111 | 219 bmp_iter_next (sbitmap_iterator *i, unsigned *bit_no ATTRIBUTE_UNUSED) |
0 | 220 { |
221 i->word >>= 1; | |
222 i->bit_num++; | |
223 } | |
224 | |
225 /* Loop over all elements of SBITMAP, starting with MIN. In each | |
226 iteration, N is set to the index of the bit being visited. ITER is | |
227 an instance of sbitmap_iterator used to iterate the bitmap. */ | |
228 | |
111 | 229 #ifndef EXECUTE_IF_SET_IN_BITMAP |
230 /* See bitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */ | |
231 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \ | |
232 for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \ | |
233 bmp_iter_set (&(ITER), &(BITNUM)); \ | |
234 bmp_iter_next (&(ITER), &(BITNUM))) | |
235 #endif | |
236 | |
237 inline void sbitmap_free (sbitmap map) | |
238 { | |
239 free (map); | |
240 } | |
0 | 241 |
111 | 242 inline void sbitmap_vector_free (sbitmap * vec) |
243 { | |
244 free (vec); | |
245 } | |
0 | 246 |
111 | 247 extern void dump_bitmap (FILE *, const_sbitmap); |
248 extern void debug_raw (const simple_bitmap_def &ref); | |
249 extern void debug_raw (const simple_bitmap_def *ptr); | |
250 extern void dump_bitmap_file (FILE *, const_sbitmap); | |
251 extern void debug (const simple_bitmap_def &ref); | |
252 extern void debug (const simple_bitmap_def *ptr); | |
253 extern void dump_bitmap_vector (FILE *, const char *, const char *, sbitmap *, | |
0 | 254 int); |
255 extern sbitmap sbitmap_alloc (unsigned int); | |
256 extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int); | |
257 extern sbitmap sbitmap_resize (sbitmap, unsigned int, int); | |
111 | 258 extern void bitmap_copy (sbitmap, const_sbitmap); |
259 extern int bitmap_equal_p (const_sbitmap, const_sbitmap); | |
260 extern unsigned int bitmap_count_bits (const_sbitmap); | |
261 extern bool bitmap_empty_p (const_sbitmap); | |
262 extern void bitmap_clear (sbitmap); | |
263 extern void bitmap_clear_range (sbitmap, unsigned, unsigned); | |
264 extern void bitmap_set_range (sbitmap, unsigned, unsigned); | |
265 extern void bitmap_ones (sbitmap); | |
266 extern void bitmap_vector_clear (sbitmap *, unsigned int); | |
267 extern void bitmap_vector_ones (sbitmap *, unsigned int); | |
0 | 268 |
111 | 269 extern bool bitmap_ior_and_compl (sbitmap, const_sbitmap, |
270 const_sbitmap, const_sbitmap); | |
271 extern void bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap); | |
272 extern void bitmap_not (sbitmap, const_sbitmap); | |
273 extern bool bitmap_or_and (sbitmap, const_sbitmap, | |
274 const_sbitmap, const_sbitmap); | |
275 extern bool bitmap_and_or (sbitmap, const_sbitmap, | |
276 const_sbitmap, const_sbitmap); | |
277 extern bool bitmap_intersect_p (const_sbitmap, const_sbitmap); | |
278 extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap); | |
279 extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap); | |
280 extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap); | |
281 extern bool bitmap_subset_p (const_sbitmap, const_sbitmap); | |
282 extern bool bitmap_bit_in_range_p (const_sbitmap, unsigned int, unsigned int); | |
283 | |
284 extern int bitmap_first_set_bit (const_sbitmap); | |
285 extern int bitmap_last_set_bit (const_sbitmap); | |
0 | 286 |
111 | 287 extern void debug_bitmap (const_sbitmap); |
288 extern sbitmap sbitmap_realloc (sbitmap, unsigned int); | |
0 | 289 |
111 | 290 /* a class that ties the lifetime of a sbitmap to its scope. */ |
291 class auto_sbitmap | |
292 { | |
293 public: | |
294 explicit auto_sbitmap (unsigned int size) : | |
295 m_bitmap (sbitmap_alloc (size)) {} | |
296 ~auto_sbitmap () { sbitmap_free (m_bitmap); } | |
0 | 297 |
111 | 298 /* Allow calling sbitmap functions on our bitmap. */ |
299 operator sbitmap () { return m_bitmap; } | |
0 | 300 |
111 | 301 private: |
302 /* Prevent making a copy that refers to our sbitmap. */ | |
303 auto_sbitmap (const auto_sbitmap &); | |
304 auto_sbitmap &operator = (const auto_sbitmap &); | |
305 #if __cplusplus >= 201103L | |
306 auto_sbitmap (auto_sbitmap &&); | |
307 auto_sbitmap &operator = (auto_sbitmap &&); | |
308 #endif | |
0 | 309 |
111 | 310 /* The bitmap we are managing. */ |
311 sbitmap m_bitmap; | |
312 }; | |
0 | 313 |
314 #endif /* ! GCC_SBITMAP_H */ |