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