]>
Commit | Line | Data |
---|---|---|
5f6c11d6 | 1 | /* Simple bitmaps. |
e360ab39 | 2 | Copyright (C) 1999, 2000, 2002, 2003 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 | |
8 | Software Foundation; either version 2, or (at your option) any later | |
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 | |
1322177d LB |
17 | along with GCC; see the file COPYING. If not, write to the Free |
18 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
5f6c11d6 RH |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
4977bab6 ZW |
23 | #include "coretypes.h" |
24 | #include "tm.h" | |
5f6c11d6 RH |
25 | #include "rtl.h" |
26 | #include "flags.h" | |
efc9bd41 | 27 | #include "hard-reg-set.h" |
5f6c11d6 RH |
28 | #include "basic-block.h" |
29 | ||
30 | /* Bitmap manipulation routines. */ | |
31 | ||
32 | /* Allocate a simple bitmap of N_ELMS bits. */ | |
33 | ||
34 | sbitmap | |
46c5ad27 | 35 | sbitmap_alloc (unsigned int n_elms) |
5f6c11d6 | 36 | { |
08158df3 | 37 | unsigned int bytes, size, amt; |
5f6c11d6 RH |
38 | sbitmap bmap; |
39 | ||
40 | size = SBITMAP_SET_SIZE (n_elms); | |
41 | bytes = size * sizeof (SBITMAP_ELT_TYPE); | |
42 | amt = (sizeof (struct simple_bitmap_def) | |
43 | + bytes - sizeof (SBITMAP_ELT_TYPE)); | |
703ad42b | 44 | bmap = xmalloc (amt); |
5f6c11d6 RH |
45 | bmap->n_bits = n_elms; |
46 | bmap->size = size; | |
47 | bmap->bytes = bytes; | |
48 | return bmap; | |
49 | } | |
50 | ||
e360ab39 RS |
51 | /* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the |
52 | size of BMAP, clear the new bits to zero if the DEF argument | |
53 | is zero, and set them to one otherwise. */ | |
54 | ||
55 | sbitmap | |
46c5ad27 | 56 | sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) |
e360ab39 RS |
57 | { |
58 | unsigned int bytes, size, amt; | |
59 | unsigned int last_bit; | |
60 | ||
61 | size = SBITMAP_SET_SIZE (n_elms); | |
62 | bytes = size * sizeof (SBITMAP_ELT_TYPE); | |
63 | if (bytes > bmap->bytes) | |
64 | { | |
65 | amt = (sizeof (struct simple_bitmap_def) | |
66 | + bytes - sizeof (SBITMAP_ELT_TYPE)); | |
703ad42b | 67 | bmap = xrealloc (bmap, amt); |
e360ab39 RS |
68 | } |
69 | ||
70 | if (n_elms > bmap->n_bits) | |
71 | { | |
72 | if (def) | |
73 | { | |
fad205ff | 74 | memset (bmap->elms + bmap->size, -1, bytes - bmap->bytes); |
e360ab39 RS |
75 | |
76 | /* Set the new bits if the original last element. */ | |
77 | last_bit = bmap->n_bits % SBITMAP_ELT_BITS; | |
78 | if (last_bit) | |
79 | bmap->elms[bmap->size - 1] | |
80 | |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); | |
81 | ||
82 | /* Clear the unused bit in the new last element. */ | |
83 | last_bit = n_elms % SBITMAP_ELT_BITS; | |
84 | if (last_bit) | |
85 | bmap->elms[size - 1] | |
86 | &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); | |
87 | } | |
88 | else | |
fad205ff | 89 | memset (bmap->elms + bmap->size, 0, bytes - bmap->bytes); |
e360ab39 RS |
90 | } |
91 | else if (n_elms < bmap->n_bits) | |
92 | { | |
3dc575ff | 93 | /* Clear the surplus bits in the last word. */ |
e360ab39 RS |
94 | last_bit = n_elms % SBITMAP_ELT_BITS; |
95 | if (last_bit) | |
96 | bmap->elms[size - 1] | |
97 | &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); | |
98 | } | |
99 | ||
100 | bmap->n_bits = n_elms; | |
101 | bmap->size = size; | |
102 | bmap->bytes = bytes; | |
103 | return bmap; | |
104 | } | |
105 | ||
5f6c11d6 RH |
106 | /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */ |
107 | ||
108 | sbitmap * | |
46c5ad27 | 109 | sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms) |
5f6c11d6 | 110 | { |
08158df3 | 111 | unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes; |
5f6c11d6 RH |
112 | sbitmap *bitmap_vector; |
113 | ||
114 | size = SBITMAP_SET_SIZE (n_elms); | |
115 | bytes = size * sizeof (SBITMAP_ELT_TYPE); | |
116 | elm_bytes = (sizeof (struct simple_bitmap_def) | |
117 | + bytes - sizeof (SBITMAP_ELT_TYPE)); | |
118 | vector_bytes = n_vecs * sizeof (sbitmap *); | |
119 | ||
120 | /* Round up `vector_bytes' to account for the alignment requirements | |
121 | of an sbitmap. One could allocate the vector-table and set of sbitmaps | |
122 | separately, but that requires maintaining two pointers or creating | |
123 | a cover struct to hold both pointers (so our result is still just | |
124 | one pointer). Neither is a bad idea, but this is simpler for now. */ | |
125 | { | |
126 | /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */ | |
127 | struct { char x; SBITMAP_ELT_TYPE y; } align; | |
128 | int alignment = (char *) & align.y - & align.x; | |
129 | vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1); | |
130 | } | |
131 | ||
132 | amt = vector_bytes + (n_vecs * elm_bytes); | |
703ad42b | 133 | bitmap_vector = xmalloc (amt); |
5f6c11d6 | 134 | |
08158df3 | 135 | for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes) |
5f6c11d6 RH |
136 | { |
137 | sbitmap b = (sbitmap) ((char *) bitmap_vector + offset); | |
08158df3 | 138 | |
5f6c11d6 RH |
139 | bitmap_vector[i] = b; |
140 | b->n_bits = n_elms; | |
141 | b->size = size; | |
142 | b->bytes = bytes; | |
143 | } | |
144 | ||
145 | return bitmap_vector; | |
146 | } | |
147 | ||
148 | /* Copy sbitmap SRC to DST. */ | |
149 | ||
150 | void | |
46c5ad27 | 151 | sbitmap_copy (sbitmap dst, sbitmap src) |
5f6c11d6 | 152 | { |
7c5b92c4 | 153 | memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size); |
5f6c11d6 RH |
154 | } |
155 | ||
2d76cb1a | 156 | /* Determine if a == b. */ |
b2d57793 | 157 | int |
46c5ad27 | 158 | sbitmap_equal (sbitmap a, sbitmap b) |
b2d57793 DB |
159 | { |
160 | return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size); | |
161 | } | |
b47374fa | 162 | |
5f6c11d6 RH |
163 | /* Zero all elements in a bitmap. */ |
164 | ||
165 | void | |
46c5ad27 | 166 | sbitmap_zero (sbitmap bmap) |
5f6c11d6 | 167 | { |
fad205ff | 168 | memset (bmap->elms, 0, bmap->bytes); |
5f6c11d6 RH |
169 | } |
170 | ||
08158df3 | 171 | /* Set all elements in a bitmap to ones. */ |
5f6c11d6 RH |
172 | |
173 | void | |
46c5ad27 | 174 | sbitmap_ones (sbitmap bmap) |
5f6c11d6 | 175 | { |
393f3ad5 RH |
176 | unsigned int last_bit; |
177 | ||
fad205ff | 178 | memset (bmap->elms, -1, bmap->bytes); |
393f3ad5 | 179 | |
08158df3 | 180 | last_bit = bmap->n_bits % SBITMAP_ELT_BITS; |
393f3ad5 | 181 | if (last_bit) |
08158df3 RK |
182 | bmap->elms[bmap->size - 1] |
183 | = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); | |
5f6c11d6 RH |
184 | } |
185 | ||
186 | /* Zero a vector of N_VECS bitmaps. */ | |
187 | ||
188 | void | |
46c5ad27 | 189 | sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs) |
5f6c11d6 | 190 | { |
08158df3 | 191 | unsigned int i; |
5f6c11d6 RH |
192 | |
193 | for (i = 0; i < n_vecs; i++) | |
194 | sbitmap_zero (bmap[i]); | |
195 | } | |
196 | ||
08158df3 | 197 | /* Set a vector of N_VECS bitmaps to ones. */ |
5f6c11d6 RH |
198 | |
199 | void | |
46c5ad27 | 200 | sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs) |
5f6c11d6 | 201 | { |
08158df3 | 202 | unsigned int i; |
5f6c11d6 RH |
203 | |
204 | for (i = 0; i < n_vecs; i++) | |
205 | sbitmap_ones (bmap[i]); | |
206 | } | |
207 | ||
208 | /* Set DST to be A union (B - C). | |
209 | DST = A | (B & ~C). | |
b47374fa | 210 | Returns true if any change is made. */ |
5f6c11d6 | 211 | |
b47374fa | 212 | bool |
46c5ad27 | 213 | sbitmap_union_of_diff_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) |
5f6c11d6 | 214 | { |
b47374fa RH |
215 | unsigned int i, n = dst->size; |
216 | sbitmap_ptr dstp = dst->elms; | |
217 | sbitmap_ptr ap = a->elms; | |
218 | sbitmap_ptr bp = b->elms; | |
219 | sbitmap_ptr cp = c->elms; | |
220 | SBITMAP_ELT_TYPE changed = 0; | |
221 | ||
222 | for (i = 0; i < n; i++) | |
5f6c11d6 | 223 | { |
08158df3 | 224 | SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++); |
b47374fa RH |
225 | changed |= *dstp ^ tmp; |
226 | *dstp++ = tmp; | |
5f6c11d6 | 227 | } |
08158df3 | 228 | |
b47374fa RH |
229 | return changed != 0; |
230 | } | |
231 | ||
232 | void | |
46c5ad27 | 233 | sbitmap_union_of_diff (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) |
b47374fa RH |
234 | { |
235 | unsigned int i, n = dst->size; | |
236 | sbitmap_ptr dstp = dst->elms; | |
237 | sbitmap_ptr ap = a->elms; | |
238 | sbitmap_ptr bp = b->elms; | |
239 | sbitmap_ptr cp = c->elms; | |
240 | ||
241 | for (i = 0; i < n; i++) | |
242 | *dstp++ = *ap++ | (*bp++ & ~*cp++); | |
5f6c11d6 RH |
243 | } |
244 | ||
245 | /* Set bitmap DST to the bitwise negation of the bitmap SRC. */ | |
246 | ||
247 | void | |
46c5ad27 | 248 | sbitmap_not (sbitmap dst, sbitmap src) |
5f6c11d6 | 249 | { |
b47374fa RH |
250 | unsigned int i, n = dst->size; |
251 | sbitmap_ptr dstp = dst->elms; | |
252 | sbitmap_ptr srcp = src->elms; | |
315d849a | 253 | unsigned int last_bit; |
5f6c11d6 | 254 | |
b47374fa RH |
255 | for (i = 0; i < n; i++) |
256 | *dstp++ = ~*srcp++; | |
315d849a MH |
257 | |
258 | /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones. */ | |
259 | last_bit = src->n_bits % SBITMAP_ELT_BITS; | |
260 | if (last_bit) | |
261 | dst->elms[n-1] = dst->elms[n-1] | |
262 | & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); | |
5f6c11d6 RH |
263 | } |
264 | ||
265 | /* Set the bits in DST to be the difference between the bits | |
08158df3 | 266 | in A and the bits in B. i.e. dst = a & (~b). */ |
5f6c11d6 RH |
267 | |
268 | void | |
46c5ad27 | 269 | sbitmap_difference (sbitmap dst, sbitmap a, sbitmap b) |
5f6c11d6 | 270 | { |
ed8d2920 MM |
271 | unsigned int i, dst_size = dst->size; |
272 | unsigned int min_size = dst->size; | |
b47374fa RH |
273 | sbitmap_ptr dstp = dst->elms; |
274 | sbitmap_ptr ap = a->elms; | |
275 | sbitmap_ptr bp = b->elms; | |
46c5ad27 | 276 | |
ed8d2920 MM |
277 | /* A should be at least as large as DEST, to have a defined source. */ |
278 | if (a->size < dst_size) | |
279 | abort (); | |
280 | /* If minuend is smaller, we simply pretend it to be zero bits, i.e. | |
281 | only copy the subtrahend into dest. */ | |
282 | if (b->size < min_size) | |
283 | min_size = b->size; | |
284 | for (i = 0; i < min_size; i++) | |
285 | *dstp++ = *ap++ & (~*bp++); | |
286 | /* Now fill the rest of dest from A, if B was too short. | |
287 | This makes sense only when destination and A differ. */ | |
288 | if (dst != a && i != dst_size) | |
289 | for (; i < dst_size; i++) | |
290 | *dstp++ = *ap++; | |
5f6c11d6 RH |
291 | } |
292 | ||
393f3ad5 | 293 | /* Set DST to be (A and B). |
0e9e1e0a | 294 | Return nonzero if any change is made. */ |
5f6c11d6 | 295 | |
b47374fa | 296 | bool |
46c5ad27 | 297 | sbitmap_a_and_b_cg (sbitmap dst, sbitmap a, sbitmap b) |
5f6c11d6 | 298 | { |
b47374fa RH |
299 | unsigned int i, n = dst->size; |
300 | sbitmap_ptr dstp = dst->elms; | |
301 | sbitmap_ptr ap = a->elms; | |
302 | sbitmap_ptr bp = b->elms; | |
303 | SBITMAP_ELT_TYPE changed = 0; | |
5f6c11d6 | 304 | |
b47374fa | 305 | for (i = 0; i < n; i++) |
5f6c11d6 | 306 | { |
08158df3 | 307 | SBITMAP_ELT_TYPE tmp = *ap++ & *bp++; |
315d849a | 308 | changed |= *dstp ^ tmp; |
b47374fa | 309 | *dstp++ = tmp; |
5f6c11d6 | 310 | } |
08158df3 | 311 | |
b47374fa RH |
312 | return changed != 0; |
313 | } | |
314 | ||
315 | void | |
46c5ad27 | 316 | sbitmap_a_and_b (sbitmap dst, sbitmap a, sbitmap b) |
b47374fa RH |
317 | { |
318 | unsigned int i, n = dst->size; | |
319 | sbitmap_ptr dstp = dst->elms; | |
320 | sbitmap_ptr ap = a->elms; | |
321 | sbitmap_ptr bp = b->elms; | |
322 | ||
323 | for (i = 0; i < n; i++) | |
324 | *dstp++ = *ap++ & *bp++; | |
5f6c11d6 | 325 | } |
08158df3 | 326 | |
b2d57793 | 327 | /* Set DST to be (A xor B)). |
0e9e1e0a | 328 | Return nonzero if any change is made. */ |
b2d57793 | 329 | |
b47374fa | 330 | bool |
46c5ad27 | 331 | sbitmap_a_xor_b_cg (sbitmap dst, sbitmap a, sbitmap b) |
b2d57793 | 332 | { |
b47374fa RH |
333 | unsigned int i, n = dst->size; |
334 | sbitmap_ptr dstp = dst->elms; | |
335 | sbitmap_ptr ap = a->elms; | |
336 | sbitmap_ptr bp = b->elms; | |
337 | SBITMAP_ELT_TYPE changed = 0; | |
338 | ||
339 | for (i = 0; i < n; i++) | |
b2d57793 DB |
340 | { |
341 | SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++; | |
315d849a | 342 | changed |= *dstp ^ tmp; |
b47374fa | 343 | *dstp++ = tmp; |
b2d57793 | 344 | } |
b47374fa RH |
345 | |
346 | return changed != 0; | |
347 | } | |
348 | ||
349 | void | |
46c5ad27 | 350 | sbitmap_a_xor_b (sbitmap dst, sbitmap a, sbitmap b) |
b47374fa RH |
351 | { |
352 | unsigned int i, n = dst->size; | |
353 | sbitmap_ptr dstp = dst->elms; | |
354 | sbitmap_ptr ap = a->elms; | |
355 | sbitmap_ptr bp = b->elms; | |
356 | ||
357 | for (i = 0; i < n; i++) | |
358 | *dstp++ = *ap++ ^ *bp++; | |
b2d57793 DB |
359 | } |
360 | ||
5f6c11d6 | 361 | /* Set DST to be (A or B)). |
0e9e1e0a | 362 | Return nonzero if any change is made. */ |
5f6c11d6 | 363 | |
b47374fa | 364 | bool |
46c5ad27 | 365 | sbitmap_a_or_b_cg (sbitmap dst, sbitmap a, sbitmap b) |
5f6c11d6 | 366 | { |
b47374fa RH |
367 | unsigned int i, n = dst->size; |
368 | sbitmap_ptr dstp = dst->elms; | |
369 | sbitmap_ptr ap = a->elms; | |
370 | sbitmap_ptr bp = b->elms; | |
371 | SBITMAP_ELT_TYPE changed = 0; | |
5f6c11d6 | 372 | |
b47374fa | 373 | for (i = 0; i < n; i++) |
5f6c11d6 | 374 | { |
08158df3 | 375 | SBITMAP_ELT_TYPE tmp = *ap++ | *bp++; |
315d849a | 376 | changed |= *dstp ^ tmp; |
b47374fa | 377 | *dstp++ = tmp; |
5f6c11d6 | 378 | } |
08158df3 | 379 | |
b47374fa RH |
380 | return changed != 0; |
381 | } | |
382 | ||
383 | void | |
46c5ad27 | 384 | sbitmap_a_or_b (sbitmap dst, sbitmap a, sbitmap b) |
b47374fa RH |
385 | { |
386 | unsigned int i, n = dst->size; | |
387 | sbitmap_ptr dstp = dst->elms; | |
388 | sbitmap_ptr ap = a->elms; | |
389 | sbitmap_ptr bp = b->elms; | |
390 | ||
391 | for (i = 0; i < n; i++) | |
392 | *dstp++ = *ap++ | *bp++; | |
5f6c11d6 | 393 | } |
08158df3 | 394 | |
0e9e1e0a | 395 | /* Return nonzero if A is a subset of B. */ |
4dc9341c | 396 | |
b47374fa | 397 | bool |
46c5ad27 | 398 | sbitmap_a_subset_b_p (sbitmap a, sbitmap b) |
4dc9341c | 399 | { |
b47374fa | 400 | unsigned int i, n = a->size; |
4dc9341c MH |
401 | sbitmap_ptr ap, bp; |
402 | ||
b47374fa | 403 | for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++) |
a4ff8d98 | 404 | if ((*ap | *bp) != *bp) |
b47374fa | 405 | return false; |
08158df3 | 406 | |
b47374fa | 407 | return true; |
4dc9341c | 408 | } |
5f6c11d6 RH |
409 | |
410 | /* Set DST to be (A or (B and C)). | |
0e9e1e0a | 411 | Return nonzero if any change is made. */ |
5f6c11d6 | 412 | |
b47374fa | 413 | bool |
46c5ad27 | 414 | sbitmap_a_or_b_and_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) |
5f6c11d6 | 415 | { |
b47374fa RH |
416 | unsigned int i, n = dst->size; |
417 | sbitmap_ptr dstp = dst->elms; | |
418 | sbitmap_ptr ap = a->elms; | |
419 | sbitmap_ptr bp = b->elms; | |
420 | sbitmap_ptr cp = c->elms; | |
421 | SBITMAP_ELT_TYPE changed = 0; | |
422 | ||
423 | for (i = 0; i < n; i++) | |
5f6c11d6 | 424 | { |
08158df3 | 425 | SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++); |
b47374fa RH |
426 | changed |= *dstp ^ tmp; |
427 | *dstp++ = tmp; | |
5f6c11d6 | 428 | } |
08158df3 | 429 | |
b47374fa RH |
430 | return changed != 0; |
431 | } | |
432 | ||
433 | void | |
46c5ad27 | 434 | sbitmap_a_or_b_and_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) |
b47374fa RH |
435 | { |
436 | unsigned int i, n = dst->size; | |
437 | sbitmap_ptr dstp = dst->elms; | |
438 | sbitmap_ptr ap = a->elms; | |
439 | sbitmap_ptr bp = b->elms; | |
440 | sbitmap_ptr cp = c->elms; | |
441 | ||
442 | for (i = 0; i < n; i++) | |
443 | *dstp++ = *ap++ | (*bp++ & *cp++); | |
5f6c11d6 RH |
444 | } |
445 | ||
08158df3 | 446 | /* Set DST to be (A and (B or C)). |
0e9e1e0a | 447 | Return nonzero if any change is made. */ |
5f6c11d6 | 448 | |
b47374fa | 449 | bool |
46c5ad27 | 450 | sbitmap_a_and_b_or_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) |
5f6c11d6 | 451 | { |
b47374fa RH |
452 | unsigned int i, n = dst->size; |
453 | sbitmap_ptr dstp = dst->elms; | |
454 | sbitmap_ptr ap = a->elms; | |
455 | sbitmap_ptr bp = b->elms; | |
456 | sbitmap_ptr cp = c->elms; | |
457 | SBITMAP_ELT_TYPE changed = 0; | |
458 | ||
459 | for (i = 0; i < n; i++) | |
5f6c11d6 | 460 | { |
08158df3 | 461 | SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++); |
b47374fa RH |
462 | changed |= *dstp ^ tmp; |
463 | *dstp++ = tmp; | |
5f6c11d6 | 464 | } |
08158df3 | 465 | |
b47374fa RH |
466 | return changed != 0; |
467 | } | |
468 | ||
469 | void | |
46c5ad27 | 470 | sbitmap_a_and_b_or_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) |
b47374fa RH |
471 | { |
472 | unsigned int i, n = dst->size; | |
473 | sbitmap_ptr dstp = dst->elms; | |
474 | sbitmap_ptr ap = a->elms; | |
475 | sbitmap_ptr bp = b->elms; | |
476 | sbitmap_ptr cp = c->elms; | |
477 | ||
478 | for (i = 0; i < n; i++) | |
479 | *dstp++ = *ap++ & (*bp++ | *cp++); | |
5f6c11d6 RH |
480 | } |
481 | ||
b2d57793 | 482 | #ifdef IN_GCC |
36349f8b AM |
483 | /* Set the bitmap DST to the intersection of SRC of successors of |
484 | block number BB, using the new flow graph structures. */ | |
485 | ||
486 | void | |
46c5ad27 | 487 | sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb) |
36349f8b AM |
488 | { |
489 | basic_block b = BASIC_BLOCK (bb); | |
08158df3 RK |
490 | unsigned int set_size = dst->size; |
491 | edge e; | |
36349f8b | 492 | |
08158df3 | 493 | for (e = b->succ; e != 0; e = e->succ_next) |
36349f8b AM |
494 | { |
495 | if (e->dest == EXIT_BLOCK_PTR) | |
786de7eb | 496 | continue; |
08158df3 | 497 | |
0b17ab2f | 498 | sbitmap_copy (dst, src[e->dest->index]); |
36349f8b AM |
499 | break; |
500 | } | |
08158df3 RK |
501 | |
502 | if (e == 0) | |
36349f8b AM |
503 | sbitmap_ones (dst); |
504 | else | |
08158df3 RK |
505 | for (e = e->succ_next; e != 0; e = e->succ_next) |
506 | { | |
507 | unsigned int i; | |
508 | sbitmap_ptr p, r; | |
509 | ||
510 | if (e->dest == EXIT_BLOCK_PTR) | |
511 | continue; | |
512 | ||
0b17ab2f | 513 | p = src[e->dest->index]->elms; |
08158df3 RK |
514 | r = dst->elms; |
515 | for (i = 0; i < set_size; i++) | |
516 | *r++ &= *p++; | |
517 | } | |
36349f8b AM |
518 | } |
519 | ||
520 | /* Set the bitmap DST to the intersection of SRC of predecessors of | |
521 | block number BB, using the new flow graph structures. */ | |
522 | ||
523 | void | |
46c5ad27 | 524 | sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb) |
36349f8b AM |
525 | { |
526 | basic_block b = BASIC_BLOCK (bb); | |
08158df3 RK |
527 | unsigned int set_size = dst->size; |
528 | edge e; | |
36349f8b | 529 | |
08158df3 | 530 | for (e = b->pred; e != 0; e = e->pred_next) |
36349f8b | 531 | { |
08158df3 | 532 | if (e->src == ENTRY_BLOCK_PTR) |
786de7eb | 533 | continue; |
08158df3 | 534 | |
0b17ab2f | 535 | sbitmap_copy (dst, src[e->src->index]); |
36349f8b AM |
536 | break; |
537 | } | |
08158df3 RK |
538 | |
539 | if (e == 0) | |
36349f8b AM |
540 | sbitmap_ones (dst); |
541 | else | |
08158df3 RK |
542 | for (e = e->pred_next; e != 0; e = e->pred_next) |
543 | { | |
544 | unsigned int i; | |
545 | sbitmap_ptr p, r; | |
546 | ||
547 | if (e->src == ENTRY_BLOCK_PTR) | |
548 | continue; | |
549 | ||
0b17ab2f | 550 | p = src[e->src->index]->elms; |
08158df3 RK |
551 | r = dst->elms; |
552 | for (i = 0; i < set_size; i++) | |
553 | *r++ &= *p++; | |
554 | } | |
36349f8b AM |
555 | } |
556 | ||
557 | /* Set the bitmap DST to the union of SRC of successors of | |
558 | block number BB, using the new flow graph structures. */ | |
559 | ||
560 | void | |
46c5ad27 | 561 | sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb) |
36349f8b AM |
562 | { |
563 | basic_block b = BASIC_BLOCK (bb); | |
08158df3 RK |
564 | unsigned int set_size = dst->size; |
565 | edge e; | |
36349f8b | 566 | |
08158df3 | 567 | for (e = b->succ; e != 0; e = e->succ_next) |
36349f8b AM |
568 | { |
569 | if (e->dest == EXIT_BLOCK_PTR) | |
786de7eb | 570 | continue; |
08158df3 | 571 | |
0b17ab2f | 572 | sbitmap_copy (dst, src[e->dest->index]); |
36349f8b AM |
573 | break; |
574 | } | |
08158df3 RK |
575 | |
576 | if (e == 0) | |
36349f8b AM |
577 | sbitmap_zero (dst); |
578 | else | |
08158df3 RK |
579 | for (e = e->succ_next; e != 0; e = e->succ_next) |
580 | { | |
581 | unsigned int i; | |
582 | sbitmap_ptr p, r; | |
583 | ||
584 | if (e->dest == EXIT_BLOCK_PTR) | |
585 | continue; | |
586 | ||
0b17ab2f | 587 | p = src[e->dest->index]->elms; |
08158df3 RK |
588 | r = dst->elms; |
589 | for (i = 0; i < set_size; i++) | |
590 | *r++ |= *p++; | |
591 | } | |
36349f8b AM |
592 | } |
593 | ||
594 | /* Set the bitmap DST to the union of SRC of predecessors of | |
595 | block number BB, using the new flow graph structures. */ | |
596 | ||
597 | void | |
46c5ad27 | 598 | sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb) |
36349f8b AM |
599 | { |
600 | basic_block b = BASIC_BLOCK (bb); | |
08158df3 RK |
601 | unsigned int set_size = dst->size; |
602 | edge e; | |
36349f8b | 603 | |
08158df3 | 604 | for (e = b->pred; e != 0; e = e->pred_next) |
36349f8b AM |
605 | { |
606 | if (e->src== ENTRY_BLOCK_PTR) | |
786de7eb | 607 | continue; |
08158df3 | 608 | |
0b17ab2f | 609 | sbitmap_copy (dst, src[e->src->index]); |
36349f8b AM |
610 | break; |
611 | } | |
08158df3 RK |
612 | |
613 | if (e == 0) | |
36349f8b AM |
614 | sbitmap_zero (dst); |
615 | else | |
08158df3 RK |
616 | for (e = e->pred_next; e != 0; e = e->pred_next) |
617 | { | |
618 | unsigned int i; | |
619 | sbitmap_ptr p, r; | |
620 | ||
621 | if (e->src == ENTRY_BLOCK_PTR) | |
622 | continue; | |
0b17ab2f RH |
623 | |
624 | p = src[e->src->index]->elms; | |
08158df3 RK |
625 | r = dst->elms; |
626 | for (i = 0; i < set_size; i++) | |
627 | *r++ |= *p++; | |
628 | } | |
36349f8b | 629 | } |
b2d57793 | 630 | #endif |
36349f8b | 631 | |
65169dcf JE |
632 | /* Return number of first bit set in the bitmap, -1 if none. */ |
633 | ||
634 | int | |
46c5ad27 | 635 | sbitmap_first_set_bit (sbitmap bmap) |
65169dcf | 636 | { |
08158df3 RK |
637 | unsigned int n; |
638 | ||
65169dcf JE |
639 | EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, { return n; }); |
640 | return -1; | |
641 | } | |
642 | ||
643 | /* Return number of last bit set in the bitmap, -1 if none. */ | |
644 | ||
645 | int | |
46c5ad27 | 646 | sbitmap_last_set_bit (sbitmap bmap) |
65169dcf JE |
647 | { |
648 | int i; | |
649 | SBITMAP_ELT_TYPE *ptr = bmap->elms; | |
08158df3 | 650 | |
65169dcf JE |
651 | for (i = bmap->size - 1; i >= 0; i--) |
652 | { | |
653 | SBITMAP_ELT_TYPE word = ptr[i]; | |
08158df3 RK |
654 | |
655 | if (word != 0) | |
656 | { | |
657 | unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1; | |
658 | SBITMAP_ELT_TYPE mask | |
659 | = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1); | |
660 | ||
661 | while (1) | |
662 | { | |
663 | if ((word & mask) != 0) | |
664 | return index; | |
665 | ||
666 | mask >>= 1; | |
667 | index--; | |
668 | } | |
669 | } | |
65169dcf | 670 | } |
08158df3 | 671 | |
65169dcf JE |
672 | return -1; |
673 | } | |
674 | ||
5f6c11d6 | 675 | void |
46c5ad27 | 676 | dump_sbitmap (FILE *file, sbitmap bmap) |
5f6c11d6 | 677 | { |
08158df3 RK |
678 | unsigned int i, n, j; |
679 | unsigned int set_size = bmap->size; | |
680 | unsigned int total_bits = bmap->n_bits; | |
5f6c11d6 RH |
681 | |
682 | fprintf (file, " "); | |
683 | for (i = n = 0; i < set_size && n < total_bits; i++) | |
08158df3 RK |
684 | for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++) |
685 | { | |
686 | if (n != 0 && n % 10 == 0) | |
687 | fprintf (file, " "); | |
688 | ||
689 | fprintf (file, "%d", | |
690 | (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0); | |
691 | } | |
692 | ||
5f6c11d6 RH |
693 | fprintf (file, "\n"); |
694 | } | |
695 | ||
08158df3 | 696 | void |
46c5ad27 | 697 | dump_sbitmap_file (FILE *file, sbitmap bmap) |
08158df3 RK |
698 | { |
699 | unsigned int i, pos; | |
700 | ||
ed8d2920 | 701 | fprintf (file, "n_bits = %d, set = {", bmap->n_bits); |
08158df3 RK |
702 | |
703 | for (pos = 30, i = 0; i < bmap->n_bits; i++) | |
704 | if (TEST_BIT (bmap, i)) | |
705 | { | |
706 | if (pos > 70) | |
707 | { | |
ed8d2920 | 708 | fprintf (file, "\n "); |
08158df3 RK |
709 | pos = 0; |
710 | } | |
711 | ||
ed8d2920 MM |
712 | fprintf (file, "%d ", i); |
713 | pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000); | |
08158df3 RK |
714 | } |
715 | ||
ed8d2920 MM |
716 | fprintf (file, "}\n"); |
717 | } | |
718 | ||
719 | void | |
46c5ad27 | 720 | debug_sbitmap (sbitmap bmap) |
ed8d2920 MM |
721 | { |
722 | dump_sbitmap_file (stderr, bmap); | |
08158df3 RK |
723 | } |
724 | ||
5f6c11d6 | 725 | void |
46c5ad27 AJ |
726 | dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle, |
727 | sbitmap *bmaps, int n_maps) | |
5f6c11d6 RH |
728 | { |
729 | int bb; | |
730 | ||
731 | fprintf (file, "%s\n", title); | |
732 | for (bb = 0; bb < n_maps; bb++) | |
733 | { | |
734 | fprintf (file, "%s %d\n", subtitle, bb); | |
735 | dump_sbitmap (file, bmaps[bb]); | |
736 | } | |
08158df3 | 737 | |
5f6c11d6 RH |
738 | fprintf (file, "\n"); |
739 | } |