Mercurial > hg > CbC > CbC_gcc
annotate gcc/ebitmap.c @ 63:b7f97abdc517 gcc-4.6-20100522
update gcc from gcc-4.5.0 to gcc-4.6
author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 24 May 2010 12:47:05 +0900 |
parents | 77e2b8dfacca |
children | f6334be47118 |
rev | line source |
---|---|
0 | 1 /* Sparse array-based bitmaps. |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. |
0 | 3 Contributed by Daniel Berlin <dberlin@dberlin.org> |
4 | |
5 This file is part of GCC. | |
6 | |
7 GCC is free software; you can redistribute it and/or modify it under | |
8 the terms of the GNU General Public License as published by the Free | |
9 Software Foundation; either version 3, or (at your option) any later | |
10 version. | |
11 | |
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 for more details. | |
16 | |
17 You should have received a copy of the GNU General Public License | |
18 along with GCC; see the file COPYING3. If not see | |
19 <http://www.gnu.org/licenses/>. */ | |
20 | |
21 #include "config.h" | |
22 #include "system.h" | |
23 #include "coretypes.h" | |
24 #include "tm.h" | |
25 #include "rtl.h" | |
26 #include "flags.h" | |
27 #include "obstack.h" | |
28 #include "ebitmap.h" | |
29 | |
30 /* The ebitmap data structure is a sparse bitmap structure that works | |
31 by having two pieces: | |
32 1. An array of all nonzero words in the structures, organized as | |
33 an array of HOST_WIDE_INT's. | |
34 2. A non-sparse bitmap saying which bitmap words are present in the | |
35 array. | |
36 | |
37 As a consequence of this representation, testing whether a bit | |
38 exists in the bitmap is faster than linked-list bitmaps. For bits | |
39 in words that are all zero, the time to test is O(1). For bits in | |
40 words that exist, it requires O(n/sizeof(word)) time to perform the | |
41 test (ignoring the one element cache). It also has much better | |
42 locality than linked-list bitmaps. | |
43 | |
44 To test whether a bit exists, we do the following: | |
45 1. Test whether the word the bit would appear in exists in the | |
46 bitmap (O(1) check of the mask). If not, fail. | |
47 | |
48 2. Population count the mask up to the word containing the bit, to | |
49 find the place in the array the word would be (popcount is cached, | |
50 but this is just as slow as the linked-list bitmap) | |
51 3. Test the word to see if the bit exists. | |
52 | |
53 Just like linked-list bitmaps, we cache the last element that has | |
54 been tested in order to speed up common access patterns. | |
55 | |
56 Most of the other speedups are simply due to better locality of the | |
57 single contiguous array. | |
58 | |
59 As would be expected in a structure like this, insertion into an | |
60 empty word in the middle requires moving bits to make room for the | |
61 new word. As most operations that perform sets perform them in | |
62 order, this is rarely a problem. We also take advantage of the | |
63 same element cache to make repeated sets to the same word O(1). | |
64 | |
65 Operations on the entire bitmap are also more efficient than linked | |
66 list bitmaps, as they are all operating on contiguous memory, and | |
67 can be easily vectorized. They are all O(number of words) + | |
68 O(number of bits that may end up in the destination), as the | |
69 appropriate operation is first performed on the word mask, and then | |
70 only those elements that may generate results are touched. | |
71 | |
72 Memory wise, the ebitmap starts out using less memory than the | |
73 linked-list bitmap, but its size in memory is technically bounded | |
74 by ((index of the highest bit set) / (size of a word) + (index of | |
75 the highest bit set) / ((size of a word) * (size of a word))) This | |
76 is because the mask is non-sparse. The mask could be transformed | |
77 into a sparse bitmap at the cost of making bit testing | |
78 *theoretically* slower (real world numbers have not been computed | |
79 yet as to whether it matters or not). */ | |
80 | |
81 /* #define EBITMAP_DEBUGGING */ | |
82 | |
83 /* Find the last set bit in ebitmap MAP. */ | |
84 | |
85 int | |
86 ebitmap_last_set_bit (ebitmap map) | |
87 { | |
88 unsigned int i = 0; | |
89 ebitmap_iterator ebi; | |
90 bool foundbit = false; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
91 |
0 | 92 /* This is not the fastest way to do this, we could simply look for |
93 the popcount, and start there, but this function is not used | |
94 anywhere speed critical. */ | |
95 EXECUTE_IF_SET_IN_EBITMAP (map, 0, i, ebi) | |
96 { | |
97 foundbit = true; | |
98 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
99 |
0 | 100 |
101 if (foundbit) | |
102 return i; | |
103 return -1; | |
104 } | |
105 | |
106 /* Grow or shrink the internal word array for MAP to NEWSIZE | |
107 elements. */ | |
108 | |
109 static inline void | |
110 ebitmap_array_grow (ebitmap map, unsigned int newsize) | |
111 { | |
112 if (newsize <= map->n_elts) | |
113 { | |
114 map->n_elts = newsize; | |
115 return; | |
116 } | |
117 | |
118 newsize += newsize / 4; | |
119 | |
120 map->n_elts = newsize; | |
121 map->elts = XRESIZEVEC (EBITMAP_ELT_TYPE, map->elts, newsize); | |
122 } | |
123 | |
124 /* Grow the internal word array for MAP so it is at least SIZE | |
125 elements. Will not shrink the array if it is already big | |
126 enough. */ | |
127 | |
128 static inline void | |
129 ebitmap_array_maybe_grow (ebitmap map, unsigned int size) | |
130 { | |
131 if (size >= map->n_elts) | |
132 ebitmap_array_grow (map, size + 1); | |
133 } | |
134 | |
135 /* Retrieve the IDX'th element from the word array for MAP. */ | |
136 | |
137 static inline EBITMAP_ELT_TYPE | |
138 ebitmap_array_get (ebitmap map, unsigned int idx) | |
139 { | |
140 gcc_assert (idx < map->n_elts); | |
141 return map->elts[idx]; | |
142 } | |
143 | |
144 /* Retrieve a pointer to the IDX'th element from the word array for | |
145 MAP. If the element index is greater than the size of the array, | |
146 the array will be grown to the correct size. */ | |
147 | |
148 static inline EBITMAP_ELT_TYPE * | |
149 ebitmap_array_grow_get (ebitmap map, unsigned int idx) | |
150 { | |
151 if (idx >= map->n_elts) | |
152 ebitmap_array_grow (map, idx + 1); | |
153 return &map->elts[idx]; | |
154 } | |
155 | |
156 /* Initialize the internal word array for MAP, so that it is SIZE | |
157 elements. */ | |
158 | |
159 static inline void | |
160 ebitmap_array_init (ebitmap map, unsigned int size) | |
161 { | |
162 if (size > 0) | |
163 { | |
164 map->elts = XNEWVEC (EBITMAP_ELT_TYPE, size); | |
165 map->n_elts = size; | |
166 } | |
167 else | |
168 { | |
169 map->n_elts = 0; | |
170 map->elts = NULL; | |
171 } | |
172 } | |
173 | |
174 /* Free the internal word array for MAP. */ | |
175 | |
176 static inline void | |
177 ebitmap_array_clear (ebitmap map) | |
178 { | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
179 if (map->elts) |
0 | 180 { |
181 free (map->elts); | |
182 map->elts = NULL; | |
183 } | |
184 map->n_elts = 0; | |
185 } | |
186 | |
187 /* Clear ebitmap MAP. */ | |
188 | |
189 void | |
190 ebitmap_clear (ebitmap map) | |
191 { | |
192 ebitmap_array_clear (map); | |
193 sbitmap_zero (map->wordmask); | |
194 map->wordmask = sbitmap_resize (map->wordmask, 1, 0); | |
195 map->numwords = 0; | |
196 map->cache = NULL; | |
197 map->cacheindex = 0; | |
198 } | |
199 | |
200 /* Allocate an ebitmap with enough room for SIZE bits to start out. */ | |
201 | |
202 ebitmap | |
203 ebitmap_alloc (unsigned int size) | |
204 { | |
205 ebitmap ret = XNEW (struct ebitmap_def); | |
206 if (size == 0) | |
207 size = EBITMAP_ELT_BITS; | |
208 ebitmap_array_init (ret, (size + EBITMAP_ELT_BITS - 1) / EBITMAP_ELT_BITS); | |
209 ret->wordmask = sbitmap_alloc_with_popcount (size); | |
210 sbitmap_zero (ret->wordmask); | |
211 ret->numwords = 0; | |
212 ret->cache = NULL; | |
213 ret->cacheindex = 0; | |
214 | |
215 return ret; | |
216 } | |
217 | |
218 /* Clear BIT from ebitmap MAP. */ | |
219 | |
220 void | |
221 ebitmap_clear_bit (ebitmap map, unsigned int bit) | |
222 { | |
223 unsigned int wordindex = bit / EBITMAP_ELT_BITS; | |
224 unsigned int eltwordindex = 0; | |
225 unsigned int bitindex, shift; | |
226 bool have_eltwordindex = false; | |
227 EBITMAP_ELT_TYPE *elt_ptr; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
228 |
0 | 229 /* If the bit can't exist in our bitmap, just return. */ |
230 if (map->numwords == 0) | |
231 return; | |
232 | |
233 if (wordindex >= map->wordmask->n_bits | |
234 || !TEST_BIT (map->wordmask, wordindex)) | |
235 return; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
236 |
0 | 237 if (map->cache != NULL && map->cacheindex == wordindex) |
238 elt_ptr = map->cache; | |
239 else | |
240 { | |
241 eltwordindex = sbitmap_popcount (map->wordmask, wordindex); | |
242 elt_ptr = &map->elts[eltwordindex]; | |
243 have_eltwordindex = true; | |
244 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
245 |
0 | 246 bitindex = bit % EBITMAP_ELT_BITS; |
247 shift = bitindex; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
248 |
0 | 249 *(elt_ptr) &= ~(((EBITMAP_ELT_TYPE)1) << shift); |
250 | |
251 /* Clear out the empty words. */ | |
252 if (*(elt_ptr) == 0) | |
253 { | |
254 if (!have_eltwordindex) | |
255 eltwordindex = sbitmap_popcount (map->wordmask, wordindex); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
256 |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
257 if (map->cache != NULL) |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
258 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
259 if (map->cacheindex == wordindex) |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
260 map->cache = NULL; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
261 else if (map->cacheindex > wordindex) |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
262 map->cache = map->cache - 1; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
263 } |
0 | 264 |
265 RESET_BIT (map->wordmask, wordindex); | |
266 | |
267 memmove(&map->elts[eltwordindex], &map->elts[eltwordindex + 1], | |
268 sizeof (EBITMAP_ELT_TYPE) * (map->numwords - eltwordindex)); | |
269 map->numwords--; | |
270 } | |
271 } | |
272 | |
273 /* Set BIT in ebitmap MAP. */ | |
274 | |
275 void | |
276 ebitmap_set_bit (ebitmap map, unsigned int bit) | |
277 { | |
278 unsigned int wordindex = bit / EBITMAP_ELT_BITS; | |
279 unsigned int eltwordindex; | |
280 unsigned int bitindex = bit % EBITMAP_ELT_BITS; | |
281 | |
282 /* If we have this element cached, just set the bit in it. */ | |
283 if (map->cache && map->cacheindex == wordindex) | |
284 { | |
285 (*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex; | |
286 return; | |
287 } | |
288 | |
289 /* Resize the wordmask if necessary. */ | |
290 if (wordindex >= map->wordmask->n_bits) | |
291 map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0); | |
292 | |
293 /* Allocate a new word in the array and move whatever is in it's | |
294 place, if necessary. */ | |
295 if (!TEST_BIT (map->wordmask, wordindex)) | |
296 { | |
297 unsigned long count; | |
298 unsigned int i; | |
299 | |
300 SET_BIT (map->wordmask, wordindex); | |
301 count = sbitmap_popcount (map->wordmask, wordindex); | |
302 gcc_assert (count <= map->numwords); | |
303 | |
304 for (i = map->numwords; i > count; i--) | |
305 { | |
306 EBITMAP_ELT_TYPE *newelt; | |
307 newelt = ebitmap_array_grow_get (map, i); | |
308 *newelt = ebitmap_array_get (map, i - 1); | |
309 } | |
310 map->numwords++; | |
311 eltwordindex = count; | |
312 ebitmap_array_maybe_grow (map, eltwordindex); | |
313 map->elts[eltwordindex] = 0; | |
314 } | |
315 else | |
316 { | |
317 eltwordindex = sbitmap_popcount (map->wordmask, wordindex); | |
318 } | |
319 | |
320 /* Set the actual bit. */ | |
321 bitindex = bit % EBITMAP_ELT_BITS; | |
322 | |
323 map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex; | |
324 map->cache = &map->elts[eltwordindex]; | |
325 map->cacheindex = wordindex; | |
326 } | |
327 | |
328 | |
329 /* Return true if MAP contains BIT. */ | |
330 | |
331 bool | |
332 ebitmap_bit_p (ebitmap map, unsigned int bit) | |
333 { | |
334 unsigned int wordindex = bit / EBITMAP_ELT_BITS; | |
335 unsigned int bitindex= bit % EBITMAP_ELT_BITS; | |
336 | |
337 /* Trivial empty ebitmap case. */ | |
338 if (map->numwords == 0) | |
339 return false; | |
340 | |
341 if (map->cache && map->cacheindex == wordindex) | |
342 return ((*map->cache) >> bitindex) & 1; | |
343 | |
344 /* If the wordindex is greater than the size of the wordmask, *or* | |
345 it's not set in the wordmask, this bit can't exist in our | |
346 ebitmap. */ | |
347 if (wordindex >= map->wordmask->n_bits | |
348 || !TEST_BIT (map->wordmask, wordindex)) | |
349 return false; | |
350 | |
351 /* Find the bit and test it. */ | |
352 map->cacheindex = wordindex; | |
353 wordindex = sbitmap_popcount (map->wordmask, wordindex); | |
354 map->cache = &map->elts[wordindex]; | |
355 | |
356 return (map->elts[wordindex] >> bitindex) & 1; | |
357 } | |
358 | |
359 /* Copy ebitmap SRC to DST. */ | |
360 | |
361 void | |
362 ebitmap_copy (ebitmap dst, ebitmap src) | |
363 { | |
364 /* Blow away any existing wordmask, and copy the new one. */ | |
365 sbitmap_free (dst->wordmask); | |
366 dst->wordmask = sbitmap_alloc_with_popcount (src->wordmask->n_bits); | |
367 sbitmap_copy (dst->wordmask, src->wordmask); | |
368 | |
369 /* Make sure our destination array is big enough, and then copy the | |
370 actual words. */ | |
371 ebitmap_array_grow (dst, src->numwords); | |
372 memcpy (dst->elts, src->elts, | |
373 src->numwords * sizeof (EBITMAP_ELT_TYPE)); | |
374 dst->numwords = src->numwords; | |
375 dst->cache = NULL; | |
376 } | |
377 | |
378 /* Dump ebitmap BMAP to FILE. */ | |
379 | |
380 void | |
381 dump_ebitmap (FILE *file, ebitmap bmap) | |
382 { | |
383 unsigned int pos; | |
384 unsigned int i; | |
385 int res; | |
386 unsigned int size; | |
387 | |
388 res = sbitmap_last_set_bit (bmap->wordmask); | |
389 if (res == -1) | |
390 size = 0; | |
391 else | |
392 size = (res + 1) * EBITMAP_ELT_BITS; | |
393 | |
394 fprintf (file, "n_words = %d, set = {", bmap->numwords); | |
395 | |
396 for (pos = 30, i = 0; i < size; i++) | |
397 if (ebitmap_bit_p (bmap, i)) | |
398 { | |
399 if (pos > 70) | |
400 { | |
401 fprintf (file, "\n "); | |
402 pos = 0; | |
403 } | |
404 | |
405 pos += fprintf (file, "%d ", i); | |
406 } | |
407 | |
408 fprintf (file, "}\n"); | |
409 } | |
410 | |
411 /* Dump ebitmap BMAP to stderr. */ | |
412 | |
413 void | |
414 debug_ebitmap (ebitmap bmap) | |
415 { | |
416 dump_ebitmap (stderr, bmap); | |
417 } | |
418 | |
419 /* Perform the operation DST &= SRC. */ | |
420 | |
421 void | |
422 ebitmap_and_into (ebitmap dst, ebitmap src) | |
423 { | |
424 sbitmap_iterator sbi; | |
425 unsigned int i; | |
426 unsigned int neweltindex = 0; | |
427 unsigned int dsteltindex = 0; | |
428 unsigned int srceltindex = 0; | |
429 | |
430 gcc_assert (dst != src); | |
431 | |
432 dst->cache = NULL; | |
433 | |
434 /* Short circuit the empty bitmap cases. */ | |
435 if (src->numwords == 0 || dst->numwords == 0) | |
436 { | |
437 ebitmap_clear (dst); | |
438 return; | |
439 } | |
440 | |
441 /* AND the masks, then walk the words that may actually appear in | |
442 the result, AND'ing them. */ | |
443 sbitmap_a_and_b (dst->wordmask, dst->wordmask, src->wordmask); | |
444 | |
445 EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi) | |
446 { | |
447 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++); | |
448 tmpword &= ebitmap_array_get (dst, dsteltindex++); | |
449 if (tmpword != 0) | |
450 { | |
451 EBITMAP_ELT_TYPE *dstplace; | |
452 dstplace = ebitmap_array_grow_get (dst, neweltindex++); | |
453 *dstplace = tmpword; | |
454 } | |
455 else | |
456 RESET_BIT (dst->wordmask, i); | |
457 } | |
458 #ifdef EBITMAP_DEBUGGING | |
459 { | |
460 unsigned int i; | |
461 | |
462 for (i = 0; i < dst->numwords; i++) | |
463 gcc_assert (dst->elts[i] != 0); | |
464 | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
465 sbitmap_verify_popcount (dst->wordmask); |
0 | 466 gcc_assert (sbitmap_popcount (dst->wordmask, |
467 dst->wordmask->n_bits) == dst->numwords); | |
468 } | |
469 #endif | |
470 dst->numwords = neweltindex; | |
471 } | |
472 | |
473 /* Perform the operation DST = SRC1 & SRC2. */ | |
474 | |
475 void | |
476 ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2) | |
477 { | |
478 sbitmap_iterator sbi; | |
479 unsigned int i; | |
480 unsigned int neweltindex = 0; | |
481 unsigned int src1eltindex = 0; | |
482 unsigned int src2eltindex = 0; | |
483 | |
484 dst->cache = NULL; | |
485 if (src1->numwords == 0 || src2->numwords == 0) | |
486 { | |
487 ebitmap_clear (dst); | |
488 return; | |
489 } | |
490 | |
491 dst->wordmask | |
492 = sbitmap_resize (dst->wordmask, | |
493 MIN (src1->wordmask->n_bits, src2->wordmask->n_bits), | |
494 0); | |
495 sbitmap_a_and_b (dst->wordmask, src1->wordmask, src2->wordmask); | |
496 | |
497 EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi) | |
498 { | |
499 bool src1hasword, src2hasword; | |
500 | |
501 src1hasword = TEST_BIT (src1->wordmask, i); | |
502 src2hasword = TEST_BIT (src2->wordmask, i); | |
503 | |
504 if (src1hasword && src2hasword) | |
505 { | |
506 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++); | |
507 tmpword &= ebitmap_array_get (src2, src2eltindex++); | |
508 if (tmpword != 0) | |
509 { | |
510 EBITMAP_ELT_TYPE *dstplace; | |
511 dstplace = ebitmap_array_grow_get (dst, neweltindex++); | |
512 *dstplace = tmpword; | |
513 } | |
514 else | |
515 RESET_BIT (dst->wordmask, i); | |
516 } | |
517 else if (src1hasword) | |
518 src1eltindex++; | |
519 else | |
520 src2eltindex++; | |
521 } | |
522 #ifdef EBITMAP_DEBUGGING | |
523 { | |
524 ebitmap_iterator ebi; | |
525 unsigned int i; | |
526 | |
527 for (i = 0; i < dst->numwords; i++) | |
528 gcc_assert (dst->elts[i] != 0); | |
529 | |
530 EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi) | |
531 if (ebitmap_bit_p (src2, i)) | |
532 gcc_assert (ebitmap_bit_p (dst, i)); | |
533 | |
534 for (i = 0; i < dst->numwords; i++) | |
535 gcc_assert (dst->elts[i] != 0); | |
536 | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
537 sbitmap_verify_popcount (dst->wordmask); |
0 | 538 gcc_assert (sbitmap_popcount (dst->wordmask, |
539 dst->wordmask->n_bits) == dst->numwords); | |
540 } | |
541 #endif | |
542 dst->numwords = neweltindex; | |
543 } | |
544 | |
545 /* Perform the operation DST |= SRC. Return true if any bits in DST | |
546 changed. */ | |
547 | |
548 bool | |
549 ebitmap_ior_into (ebitmap dst, ebitmap src) | |
550 { | |
551 unsigned int dstsize = dst->wordmask->n_bits; | |
552 unsigned int srcsize = src->wordmask->n_bits; | |
553 sbitmap_iterator sbi; | |
554 unsigned int i; | |
555 sbitmap tempmask; | |
556 unsigned int neweltindex = 0; | |
557 unsigned int dsteltindex = 0; | |
558 unsigned int srceltindex = 0; | |
559 bool changed = false; | |
560 EBITMAP_ELT_TYPE *newarray; | |
561 unsigned int newarraysize; | |
562 #ifdef EBITMAP_DEBUGGING | |
563 ebitmap dstcopy = ebitmap_alloc (1); | |
564 ebitmap_copy (dstcopy, dst); | |
565 #endif | |
566 | |
567 dst->cache = NULL; | |
568 if (dst == src) | |
569 return false; | |
570 | |
571 if (dst->numwords == 0 && src->numwords != 0) | |
572 { | |
573 ebitmap_copy (dst, src); | |
574 return true; | |
575 } | |
576 else if (src->numwords == 0) | |
577 return false; | |
578 | |
579 /* We can do without the temp mask if it's faster, but it would mean | |
580 touching more words in the actual dense vector. */ | |
581 tempmask = sbitmap_alloc (MAX (srcsize, dstsize)); | |
582 sbitmap_zero (tempmask); | |
583 if (srcsize == dstsize) | |
584 { | |
585 sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask); | |
586 } | |
587 else | |
588 { | |
589 dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize), | |
590 0); | |
591 if (srcsize >= dstsize) | |
592 { | |
593 sbitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size); | |
594 sbitmap_a_or_b (tempmask, tempmask, src->wordmask); | |
595 } | |
596 else | |
597 { | |
598 sbitmap_copy_n (tempmask, src->wordmask, src->wordmask->size); | |
599 sbitmap_a_or_b (tempmask, tempmask, dst->wordmask); | |
600 } | |
601 } | |
602 newarraysize = src->numwords + dst->numwords; | |
603 newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); | |
604 | |
605 EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi) | |
606 { | |
607 bool dsthasword, srchasword; | |
608 | |
609 dsthasword = (i < dst->wordmask->n_bits | |
610 && TEST_BIT (dst->wordmask, i)); | |
611 srchasword = (i < src->wordmask->n_bits | |
612 && TEST_BIT (src->wordmask, i)); | |
613 | |
614 if (dsthasword && srchasword) | |
615 { | |
616 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++); | |
617 tmpword |= ebitmap_array_get (dst, dsteltindex); | |
618 if (!changed) | |
619 changed |= tmpword != ebitmap_array_get (dst, dsteltindex); | |
620 dsteltindex++; | |
621 newarray[neweltindex++] = tmpword; | |
622 } | |
623 else if (dsthasword) | |
624 { | |
625 newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++); | |
626 } | |
627 else | |
628 { | |
629 newarray [neweltindex++] = ebitmap_array_get (src, srceltindex++); | |
630 gcc_assert (i < dst->wordmask->n_bits); | |
631 SET_BIT (dst->wordmask, i); | |
632 changed |= true; | |
633 } | |
634 } | |
635 | |
636 sbitmap_free (tempmask); | |
637 if (changed) | |
638 { | |
639 dst->numwords = neweltindex; | |
640 free (dst->elts); | |
641 dst->elts = newarray; | |
642 dst->n_elts = newarraysize; | |
643 } | |
644 else | |
645 free (newarray); | |
646 | |
647 #ifdef EBITMAP_DEBUGGING | |
648 { | |
649 ebitmap_iterator ebi; | |
650 unsigned int i; | |
651 | |
652 for (i = 0; i < dst->numwords; i++) | |
653 gcc_assert (dst->elts[i] != 0); | |
654 | |
655 EXECUTE_IF_SET_IN_EBITMAP (src, 0, i, ebi) | |
656 gcc_assert (ebitmap_bit_p (dst, i)); | |
657 EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi) | |
658 gcc_assert (ebitmap_bit_p (dst, i)); | |
659 | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
660 sbitmap_verify_popcount (dst->wordmask); |
0 | 661 gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy)); |
662 gcc_assert (sbitmap_popcount (dst->wordmask, | |
663 dst->wordmask->n_bits) == dst->numwords); | |
664 } | |
665 #endif | |
666 return changed; | |
667 } | |
668 | |
669 /* Perform the operation DST = SRC1 | SRC2. Return true if any bit | |
670 in DST has changed. */ | |
671 | |
672 bool | |
673 ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2) | |
674 { | |
675 unsigned int src1size = src1->wordmask->n_bits; | |
676 unsigned int src2size = src2->wordmask->n_bits; | |
677 sbitmap_iterator sbi; | |
678 unsigned int i; | |
679 sbitmap tempmask; | |
680 unsigned int neweltindex = 0; | |
681 unsigned int src1eltindex = 0; | |
682 unsigned int src2eltindex = 0; | |
683 bool changed = false; | |
684 EBITMAP_ELT_TYPE *newarray; | |
685 unsigned int newarraysize; | |
686 #ifdef EBITMAP_DEBUGGING | |
687 ebitmap dstcopy = ebitmap_alloc (1); | |
688 ebitmap_copy (dstcopy, dst); | |
689 #endif | |
690 | |
691 dst->cache = NULL; | |
692 tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size)); | |
693 sbitmap_zero (tempmask); | |
694 if (src1size == src2size) | |
695 { | |
696 sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask); | |
697 } | |
698 else | |
699 { | |
700 if (src1size >= src2size) | |
701 { | |
702 sbitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size); | |
703 sbitmap_a_or_b (tempmask, tempmask, src1->wordmask); | |
704 } | |
705 else | |
706 { | |
707 sbitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size); | |
708 sbitmap_a_or_b (tempmask, tempmask, src2->wordmask); | |
709 } | |
710 } | |
711 newarraysize = src1->numwords + src2->numwords; | |
712 newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); | |
713 | |
714 EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi) | |
715 { | |
716 bool src1hasword, src2hasword; | |
717 EBITMAP_ELT_TYPE tmpword; | |
718 src1hasword = (i < src1->wordmask->n_bits | |
719 && TEST_BIT (src1->wordmask, i)); | |
720 src2hasword = (i < src2->wordmask->n_bits | |
721 && TEST_BIT (src2->wordmask, i)); | |
722 | |
723 if (src1hasword && src2hasword) | |
724 { | |
725 tmpword = (ebitmap_array_get (src1, src1eltindex++) | |
726 | ebitmap_array_get (src2, src2eltindex++)); | |
727 newarray[neweltindex++] = tmpword; | |
728 } | |
729 else if (src1hasword) | |
730 { | |
731 tmpword = ebitmap_array_get (src1, src1eltindex++); | |
732 newarray [neweltindex++] = tmpword; | |
733 } | |
734 else | |
735 { | |
736 tmpword = ebitmap_array_get (src2, src2eltindex++); | |
737 newarray [neweltindex++] = tmpword; | |
738 } | |
739 | |
740 if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i)) | |
741 { | |
742 changed = true; | |
743 } | |
744 else if (!changed) | |
745 { | |
746 unsigned int count = sbitmap_popcount (dst->wordmask, i); | |
747 changed |= ebitmap_array_get (dst, count) != tmpword; | |
748 } | |
749 } | |
750 | |
751 if (changed) | |
752 { | |
753 sbitmap_free (dst->wordmask); | |
754 dst->wordmask = tempmask; | |
755 dst->numwords = neweltindex; | |
756 free (dst->elts); | |
757 dst->elts = newarray; | |
758 dst->n_elts = newarraysize; | |
759 } | |
760 else | |
761 { | |
762 sbitmap_free (tempmask); | |
763 free (newarray); | |
764 } | |
765 | |
766 #ifdef EBITMAP_DEBUGGING | |
767 { | |
768 ebitmap_iterator ebi; | |
769 unsigned int i; | |
770 | |
771 for (i = 0; i < dst->numwords; i++) | |
772 gcc_assert (dst->elts[i] != 0); | |
773 | |
774 EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi) | |
775 gcc_assert (ebitmap_bit_p (dst, i)); | |
776 | |
777 EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi) | |
778 gcc_assert (ebitmap_bit_p (dst, i)); | |
779 } | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
780 sbitmap_verify_popcount (dst->wordmask); |
0 | 781 gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy)); |
782 gcc_assert (sbitmap_popcount (dst->wordmask, | |
783 dst->wordmask->n_bits) == dst->numwords); | |
784 #endif | |
785 | |
786 return changed; | |
787 } | |
788 | |
789 /* Perform the operation DST &= ~SRC. Return true if any bit in DST | |
790 has changed. */ | |
791 | |
792 bool | |
793 ebitmap_and_compl_into (ebitmap dst, ebitmap src) | |
794 { | |
795 bool changed = false; | |
796 unsigned int i; | |
797 unsigned int neweltindex = 0; | |
798 unsigned int dsteltindex = 0; | |
799 sbitmap_iterator sbi; | |
800 #ifdef EBITMAP_DEBUGGING | |
801 ebitmap dstcopy = ebitmap_alloc (1); | |
802 ebitmap_copy (dstcopy, dst); | |
803 #endif | |
804 | |
805 gcc_assert (dst != src); | |
806 dst->cache = NULL; | |
807 if (src->numwords == 0) | |
808 return false; | |
809 | |
810 EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi) | |
811 { | |
812 bool srchasword; | |
813 | |
814 srchasword = (i < src->wordmask->n_bits | |
815 && TEST_BIT (src->wordmask, i)); | |
816 | |
817 if (srchasword) | |
818 { | |
819 unsigned int srccount = sbitmap_popcount (src->wordmask, i); | |
820 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex); | |
821 tmpword &= ~(ebitmap_array_get (src, srccount)); | |
822 if (!changed) | |
823 changed |= ebitmap_array_get (dst, dsteltindex) != tmpword; | |
824 dsteltindex++; | |
825 if (tmpword != 0) | |
826 { | |
827 EBITMAP_ELT_TYPE *dstplace; | |
828 dstplace = ebitmap_array_grow_get (dst, neweltindex++); | |
829 *dstplace = tmpword; | |
830 } | |
831 else | |
832 RESET_BIT (dst->wordmask, i); | |
833 } | |
834 else | |
835 { | |
836 dsteltindex++; | |
837 neweltindex++; | |
838 } | |
839 } | |
840 #ifdef EBITMAP_DEBUGGING | |
841 { | |
842 unsigned int i; | |
843 ebitmap_iterator ebi; | |
844 | |
845 EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi) | |
846 { | |
847 if (!ebitmap_bit_p (src, i)) | |
848 gcc_assert (ebitmap_bit_p (dst, i)); | |
849 } | |
850 | |
851 for (i = 0; i < dst->numwords; i++) | |
852 gcc_assert (dst->elts[i] != 0); | |
853 | |
854 gcc_assert (sbitmap_popcount (dst->wordmask, | |
855 dst->wordmask->n_bits) == neweltindex); | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
856 sbitmap_verify_popcount (dst->wordmask); |
0 | 857 gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy)); |
858 gcc_assert (sbitmap_popcount (dst->wordmask, | |
859 dst->wordmask->n_bits) == dst->numwords); | |
860 } | |
861 #endif | |
862 dst->numwords = neweltindex; | |
863 /* sbitmap_popcount (dst->wordmask, -1); */ | |
864 | |
865 return changed; | |
866 } | |
867 | |
868 /* Perform the operation DST = SRC1 & ~SRC2. Return true if any bit | |
869 in DST has changed. */ | |
870 | |
871 bool | |
872 ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2) | |
873 { | |
874 unsigned int src1size = src1->wordmask->n_bits; | |
875 sbitmap_iterator sbi; | |
876 unsigned int i; | |
877 sbitmap tempmask; | |
878 unsigned int neweltindex = 0; | |
879 unsigned int src1eltindex = 0; | |
880 bool changed = false; | |
881 EBITMAP_ELT_TYPE *newarray; | |
882 unsigned int newarraysize; | |
883 | |
884 /* XXX: Optimize like the into version. */ | |
885 dst->cache = NULL; | |
886 tempmask = sbitmap_alloc_with_popcount (src1size); | |
887 sbitmap_zero (tempmask); | |
888 sbitmap_copy (tempmask, src1->wordmask); | |
889 | |
890 newarraysize = src1->numwords; | |
891 newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); | |
892 | |
893 EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi) | |
894 { | |
895 bool src2hasword; | |
896 EBITMAP_ELT_TYPE tmpword; | |
897 | |
898 src2hasword = (i < src2->wordmask->n_bits | |
899 && TEST_BIT (src2->wordmask, i)); | |
900 | |
901 if (src2hasword) | |
902 { | |
903 unsigned int src2count = sbitmap_popcount (src2->wordmask, i); | |
904 tmpword = ebitmap_array_get (src1, src1eltindex++) | |
905 & ~(ebitmap_array_get (src2, src2count)); | |
906 if (tmpword) | |
907 { | |
908 newarray[neweltindex++] = tmpword; | |
909 } | |
910 else | |
911 RESET_BIT (tempmask, i); | |
912 | |
913 } | |
914 else | |
915 { | |
916 tmpword = ebitmap_array_get (src1, src1eltindex++); | |
917 gcc_assert (tmpword != 0); | |
918 newarray[neweltindex++] = tmpword; | |
919 } | |
920 | |
921 if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i)) | |
922 { | |
923 changed = true; | |
924 } | |
925 else if (!changed) | |
926 { | |
927 unsigned int count = sbitmap_popcount (dst->wordmask, i); | |
928 changed |= ebitmap_array_get (dst, count) != tmpword; | |
929 } | |
930 } | |
931 if (changed) | |
932 { | |
933 sbitmap_free (dst->wordmask); | |
934 dst->wordmask = tempmask; | |
935 dst->numwords = neweltindex; | |
936 free (dst->elts); | |
937 dst->elts = newarray; | |
938 dst->n_elts = newarraysize; | |
939 } | |
940 else | |
941 { | |
942 free (tempmask); | |
943 free (newarray); | |
944 } | |
945 #ifdef EBITMAP_DEBUGGING | |
946 { | |
947 unsigned int i; | |
948 ebitmap_iterator ebi; | |
949 | |
950 EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi) | |
951 { | |
952 if (!ebitmap_bit_p (src2, i)) | |
953 gcc_assert (ebitmap_bit_p (dst, i)); | |
954 } | |
955 for (i = 0; i < dst->numwords; i++) | |
956 gcc_assert (dst->elts[i] != 0); | |
957 | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
958 sbitmap_verify_popcount (dst->wordmask); |
0 | 959 gcc_assert (sbitmap_popcount (dst->wordmask, |
960 dst->wordmask->n_bits) == dst->numwords); | |
961 } | |
962 #endif | |
963 return changed; | |
964 } | |
965 | |
966 /* Perform the operation DST = A | (B & ~C). */ | |
967 | |
968 bool | |
969 ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c) | |
970 { | |
971 bool changed; | |
972 ebitmap temp = ebitmap_alloc (1); | |
973 #ifdef EBITMAP_DEBUGGING | |
974 ebitmap dstcopy = ebitmap_alloc (1); | |
975 ebitmap_copy (dstcopy, dst); | |
976 #endif | |
977 | |
978 dst->cache = NULL; | |
979 ebitmap_and_compl (temp, b, c); | |
980 changed = ebitmap_ior (dst, a, temp); | |
981 #ifdef EBITMAP_DEBUGGING | |
982 { | |
983 ebitmap_iterator ebi; | |
984 unsigned int i; | |
985 | |
986 EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi) | |
987 gcc_assert (ebitmap_bit_p (dst, i)); | |
988 | |
989 EXECUTE_IF_SET_IN_EBITMAP (b, 0, i, ebi) | |
990 if (!ebitmap_bit_p (c, i)) | |
991 gcc_assert (ebitmap_bit_p (dst, i)); | |
992 gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy)); | |
993 } | |
994 #endif | |
995 ebitmap_free (temp); | |
996 | |
997 return changed; | |
998 } | |
999 | |
1000 /* Return true if ebitmap DST is equal to ebitmap SRC. */ | |
1001 | |
1002 bool | |
1003 ebitmap_equal_p (ebitmap dst, ebitmap src) | |
1004 { | |
1005 unsigned int which = MIN (dst->wordmask->size, src->wordmask->size); | |
1006 | |
1007 if (dst->numwords != src->numwords) | |
1008 return false; | |
1009 | |
1010 /* sbitmap_equal compares up to the size of the first argument, so | |
1011 if the two sbitmaps are not equally sized, we need to pass the | |
1012 smaller one as the first argument, or it will crash. */ | |
1013 if (which == dst->wordmask->size | |
1014 && !sbitmap_equal (dst->wordmask, src->wordmask)) | |
1015 return false; | |
1016 else if (which == src->wordmask->size | |
1017 && !sbitmap_equal (src->wordmask, dst->wordmask)) | |
1018 return false; | |
1019 | |
1020 return memcmp (dst->elts, src->elts, | |
1021 dst->numwords * sizeof (EBITMAP_ELT_TYPE)) == 0; | |
1022 return true; | |
1023 } |