OSDN Git Service

2004-11-01 Andrew Pinski <pinskia@physics.uc.edu>
[pf3gnuchains/gcc-fork.git] / gcc / bitmap.h
1 /* Functions to support general ended bitmaps.
2    Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
3    Free Software Foundation, Inc.
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 2, 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 COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22 #ifndef GCC_BITMAP_H
23 #define GCC_BITMAP_H
24
25 /* Fundamental storage type for bitmap.  */
26
27 /* typedef unsigned HOST_WIDE_INT BITMAP_WORD; */
28 /* #define nBITMAP_WORD_BITS HOST_BITS_PER_WIDE_INT */
29 typedef unsigned long BITMAP_WORD;
30 #define nBITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG)
31 #define BITMAP_WORD_BITS (unsigned) nBITMAP_WORD_BITS
32
33 /* Number of words to use for each element in the linked list.  */
34
35 #ifndef BITMAP_ELEMENT_WORDS
36 #define BITMAP_ELEMENT_WORDS ((128 + nBITMAP_WORD_BITS - 1) / nBITMAP_WORD_BITS)
37 #endif
38
39 /* Number of bits in each actual element of a bitmap.  We get slightly better
40    code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if
41    bits is unsigned, assuming it is a power of 2.  */
42
43 #define BITMAP_ELEMENT_ALL_BITS \
44   ((unsigned) (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS))
45
46 /* Bitmap set element.  We use a linked list to hold only the bits that
47    are set.  This allows for use to grow the bitset dynamically without
48    having to realloc and copy a giant bit array.  The `prev' field is
49    undefined for an element on the free list.  */
50
51 typedef struct bitmap_element_def GTY(())
52 {
53   struct bitmap_element_def *next;              /* Next element.  */
54   struct bitmap_element_def *prev;              /* Previous element.  */
55   unsigned int indx;                    /* regno/BITMAP_ELEMENT_ALL_BITS.  */
56   BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set.  */
57 } bitmap_element;
58
59 /* Head of bitmap linked list.  */
60 typedef struct bitmap_head_def GTY(()) {
61   bitmap_element *first;        /* First element in linked list.  */
62   bitmap_element *current;      /* Last element looked at.  */
63   unsigned int indx;            /* Index of last element looked at.  */
64   int using_obstack;            /* Are we using an obstack or ggc for
65                                    allocation?  */
66 } bitmap_head;
67 typedef struct bitmap_head_def *bitmap;
68
69 /* Enumeration giving the various operations we support.  */
70 enum bitmap_bits {
71   BITMAP_AND,                   /* TO = FROM1 & FROM2 */
72   BITMAP_AND_COMPL,             /* TO = FROM1 & ~ FROM2 */
73   BITMAP_IOR,                   /* TO = FROM1 | FROM2 */
74   BITMAP_XOR,                   /* TO = FROM1 ^ FROM2 */
75   BITMAP_IOR_COMPL                      /* TO = FROM1 | ~FROM2 */
76 };
77
78 /* Global data */
79 extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
80
81 /* Clear a bitmap by freeing up the linked list.  */
82 extern void bitmap_clear (bitmap);
83
84 /* Copy a bitmap to another bitmap.  */
85 extern void bitmap_copy (bitmap, bitmap);
86
87 /* True if two bitmaps are identical.  */
88 extern int bitmap_equal_p (bitmap, bitmap);
89
90 #define bitmap_empty_p(MAP) (!(MAP)->first)
91
92 /* Perform an operation on two bitmaps, yielding a third.  */
93 extern int bitmap_operation (bitmap, bitmap, bitmap, enum bitmap_bits);
94
95 #define bitmap_and(DST,A,B) bitmap_operation (DST,A,B,BITMAP_AND)
96 #define bitmap_and_into(DST_SRC,B) bitmap_operation (DST_SRC,DST_SRC,B,BITMAP_AND)
97 #define bitmap_and_compl(DST,A,B) bitmap_operation (DST,A,B,BITMAP_AND_COMPL)
98 #define bitmap_and_compl_into(DST_SRC,B) bitmap_operation (DST_SRC,DST_SRC,B,BITMAP_AND_COMPL)
99 #define bitmap_ior(DST,A,B) bitmap_operation (DST,A,B,BITMAP_IOR)
100 #define bitmap_ior_into(DST_SRC,B) bitmap_operation (DST_SRC,DST_SRC,B,BITMAP_IOR)
101 #define bitmap_ior_compl(DST,A,B) bitmap_operation (DST,A,B,BITMAP_IOR_COMPL)
102 #define bitmap_xor(DST,A,B) bitmap_operation (DST,A,B,BITMAP_XOR)
103 #define bitmap_xor_into(DST_SRC,B) bitmap_operation (DST_SRC,DST_SRC,B,BITMAP_XOR)
104
105 /* `or' into one bitmap the `and' of a second bitmap witih the complement
106    of a third. Return nonzero if the bitmap changes. */
107 extern int bitmap_ior_and_compl_into (bitmap, bitmap, bitmap);
108
109 /* Clear a single register in a register set.  */
110 extern void bitmap_clear_bit (bitmap, int);
111
112 /* Set a single register in a register set.  */
113 extern void bitmap_set_bit (bitmap, int);
114
115 /* Return true if a register is set in a register set.  */
116 extern int bitmap_bit_p (bitmap, int);
117
118 /* Debug functions to print a bitmap linked list.  */
119 extern void debug_bitmap (bitmap);
120 extern void debug_bitmap_file (FILE *, bitmap);
121
122 /* Print a bitmap.  */
123 extern void bitmap_print (FILE *, bitmap, const char *, const char *);
124
125 /* Initialize a bitmap header.  If HEAD is NULL, a new header will be
126    allocated.  USING_OBSTACK indicates how elements should be allocated.  */
127 extern bitmap bitmap_initialize (bitmap head, int using_obstack);
128
129 /* Release all memory used by the bitmap obstack.  */
130 extern void bitmap_release_memory (void);
131
132 /* A few compatibility/functions macros for compatibility with sbitmaps */
133 #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
134 #define bitmap_zero(a) bitmap_clear (a)
135 #define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR)
136 #define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND)
137 extern int bitmap_union_of_diff (bitmap, bitmap, bitmap, bitmap);
138 extern int bitmap_first_set_bit (bitmap);
139 extern int bitmap_last_set_bit (bitmap);
140
141 /* Allocate a bitmap with oballoc.  */
142 #define BITMAP_OBSTACK_ALLOC(OBSTACK)                           \
143   bitmap_initialize (obstack_alloc (OBSTACK, sizeof (bitmap_head)), 1)
144
145 /* Allocate a bitmap with ggc_alloc.  */
146 #define BITMAP_GGC_ALLOC()                      \
147   bitmap_initialize (NULL, 0)
148
149 /* Allocate a bitmap with xmalloc.  */
150 #define BITMAP_XMALLOC()                                        \
151   bitmap_initialize (xmalloc (sizeof (bitmap_head)), 1)
152
153 /* Do any cleanup needed on a bitmap when it is no longer used.  */
154 #define BITMAP_FREE(BITMAP)                     \
155 do {                                            \
156   if (BITMAP)                                   \
157     {                                           \
158       bitmap_clear (BITMAP);                    \
159       (BITMAP) = 0;                             \
160     }                                           \
161 } while (0)
162
163 /* Do any cleanup needed on an xmalloced bitmap when it is no longer used.  */
164 #define BITMAP_XFREE(BITMAP)                    \
165 do {                                            \
166   if (BITMAP)                                   \
167     {                                           \
168       bitmap_clear (BITMAP);                    \
169       free (BITMAP);                            \
170       (BITMAP) = 0;                             \
171     }                                           \
172 } while (0)
173
174 /* Do any one-time initializations needed for bitmaps.  */
175 #define BITMAP_INIT_ONCE()
176
177 /* Iterator for bitmaps.  */
178
179 typedef struct
180 {
181   /* Actual elements in the bitmaps.  */
182   bitmap_element *ptr1, *ptr2;
183
184   /* Position of an actual word in the elements.  */
185   unsigned word;
186
187   /* Position of a bit corresponding to the start of word.  */
188   unsigned word_bit;
189
190   /* Position of the actual bit.  */
191   unsigned bit;
192
193   /* Contents of the actually processed word.  When finding next bit
194      it is shifted right, so that the actual bit is always the least
195      significant bit of ACTUAL.  */
196   BITMAP_WORD actual;
197 } bitmap_iterator;
198
199 /* Moves the iterator BI to the first set bit on or after the current
200    position in bitmap and returns the bit if available.  The bit is
201    found in ACTUAL field only.  */
202
203 static inline unsigned
204 bmp_iter_common_next_1 (bitmap_iterator *bi)
205 {
206   while (!(bi->actual & 1))
207     {
208       bi->actual >>= 1;
209       bi->bit++;
210     }
211
212   return bi->bit;
213 }
214
215 /* Moves the iterator BI to the first set bit on or after the current
216    position in bitmap and returns the bit if available.  */
217
218 static inline unsigned
219 bmp_iter_single_next_1 (bitmap_iterator *bi)
220 {
221   if (bi->actual)
222     return bmp_iter_common_next_1 (bi);
223
224   bi->word++;
225   bi->word_bit += BITMAP_WORD_BITS;
226
227   while (1)
228     {
229       for (;
230            bi->word < BITMAP_ELEMENT_WORDS;
231            bi->word++, bi->word_bit += BITMAP_WORD_BITS)
232         {
233           bi->actual = bi->ptr1->bits[bi->word];
234           if (bi->actual)
235             {
236               bi->bit = bi->word_bit;
237               return bmp_iter_common_next_1 (bi);
238             }
239         }
240
241       bi->ptr1 = bi->ptr1->next;
242       if (!bi->ptr1)
243         return 0;
244
245       bi->word = 0;
246       bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
247     }
248 }
249
250 /* Initializes a bitmap iterator BI for looping over bits of bitmap
251    BMP, starting with bit MIN.  Returns the first bit of BMP greater
252    or equal to MIN if there is any.  */
253
254 static inline unsigned
255 bmp_iter_single_init (bitmap_iterator *bi, bitmap bmp, unsigned min)
256 {
257   unsigned indx = min / BITMAP_ELEMENT_ALL_BITS;
258
259   for (bi->ptr1 = bmp->first;
260        bi->ptr1 && bi->ptr1->indx < indx;
261        bi->ptr1 = bi->ptr1->next)
262     continue;
263
264   if (!bi->ptr1)
265     {
266       /* To avoid warnings.  */
267       bi->word = 0;
268       bi->bit = 0;
269       bi->word_bit = 0;
270       bi->actual = 0;
271       bi->ptr2 = NULL;
272       return 0;
273     }
274
275   if (bi->ptr1->indx == indx)
276     {
277       unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx;
278       unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS;
279       unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS;
280
281       bi->word = word_in_elt;
282       bi->word_bit = min - bit_in_word;
283       bi->bit = min;
284       bi->actual = bi->ptr1->bits[word_in_elt] >> bit_in_word;
285     }
286   else
287     {
288       bi->word = 0;
289       bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
290       bi->word_bit = bi->bit;
291       bi->actual = bi->ptr1->bits[0];
292     }
293
294   return bmp_iter_single_next_1 (bi);
295 }
296
297 /* Returns true if all elements of the bitmap referred to by iterator BI
298    were processed.  */
299
300 static inline bool
301 bmp_iter_end_p (const bitmap_iterator *bi)
302 {
303   return bi->ptr1 == NULL;
304 }
305
306 /* Moves the iterator BI to the next bit of bitmap and returns the bit
307    if available.  */
308
309 static inline unsigned
310 bmp_iter_single_next (bitmap_iterator *bi)
311 {
312   bi->bit++;
313   bi->actual >>= 1;
314   return bmp_iter_single_next_1 (bi);
315 }
316
317 /* Loop over all bits in BITMAP, starting with MIN and setting BITNUM to
318    the bit number.  ITER is a bitmap iterator.  */
319
320 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)             \
321   for ((BITNUM) = bmp_iter_single_init (&(ITER), (BITMAP), (MIN));      \
322        !bmp_iter_end_p (&(ITER));                                       \
323        (BITNUM) = bmp_iter_single_next (&(ITER)))
324
325 /* Moves the iterator BI to the first set bit on or after the current
326    position in difference of bitmaps and returns the bit if available.  */
327
328 static inline unsigned
329 bmp_iter_and_not_next_1 (bitmap_iterator *bi)
330 {
331   if (bi->actual)
332     return bmp_iter_common_next_1 (bi);
333
334   bi->word++;
335   bi->word_bit += BITMAP_WORD_BITS;
336
337   while (1)
338     {
339       bitmap_element *snd;
340
341       if (bi->ptr2 && bi->ptr2->indx == bi->ptr1->indx)
342         snd = bi->ptr2;
343       else
344         snd = &bitmap_zero_bits;
345
346       for (;
347            bi->word < BITMAP_ELEMENT_WORDS;
348            bi->word++, bi->word_bit += BITMAP_WORD_BITS)
349         {
350           bi->actual = (bi->ptr1->bits[bi->word]
351                         & ~snd->bits[bi->word]);
352           if (bi->actual)
353             {
354               bi->bit = bi->word_bit;
355               return bmp_iter_common_next_1 (bi);
356             }
357         }
358
359       bi->ptr1 = bi->ptr1->next;
360       if (!bi->ptr1)
361         return 0;
362
363       while (bi->ptr2
364              && bi->ptr2->indx < bi->ptr1->indx)
365         bi->ptr2 = bi->ptr2->next;
366
367       bi->word = 0;
368       bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
369     }
370 }
371
372 /* Initializes a bitmap iterator BI for looping over bits of bitmap
373    BMP1 &~ BMP2, starting with bit MIN.  Returns the first bit of
374    BMP1 &~ BMP2 greater or equal to MIN if there is any.  */
375
376 static inline unsigned
377 bmp_iter_and_not_init (bitmap_iterator *bi, bitmap bmp1, bitmap bmp2,
378                        unsigned min)
379 {
380   unsigned indx = min / BITMAP_ELEMENT_ALL_BITS;
381
382   for (bi->ptr1 = bmp1->first;
383        bi->ptr1 && bi->ptr1->indx < indx;
384        bi->ptr1 = bi->ptr1->next)
385     continue;
386
387   if (!bi->ptr1)
388     {
389       /* To avoid warnings.  */
390       bi->word = 0;
391       bi->bit = 0;
392       bi->word_bit = 0;
393       bi->actual = 0;
394       bi->ptr2 = NULL;
395       return 0;
396     }
397
398   for (bi->ptr2 = bmp2->first;
399        bi->ptr2 && bi->ptr2->indx < bi->ptr1->indx;
400        bi->ptr2 = bi->ptr2->next)
401     continue;
402
403   if (bi->ptr1->indx == indx)
404     {
405       unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx;
406       unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS;
407       unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS;
408
409       bi->word = word_in_elt;
410       bi->word_bit = min - bit_in_word;
411       bi->bit = min;
412
413       if (bi->ptr2 && bi->ptr2->indx == indx)
414         bi->actual = (bi->ptr1->bits[word_in_elt]
415                       & ~bi->ptr2->bits[word_in_elt]) >> bit_in_word;
416       else
417        bi->actual = bi->ptr1->bits[word_in_elt] >> bit_in_word;
418     }
419   else
420     {
421       bi->word = 0;
422       bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
423       bi->word_bit = bi->bit;
424
425       if (bi->ptr2 && bi->ptr2->indx == bi->ptr1->indx)
426         bi->actual = (bi->ptr1->bits[0] & ~bi->ptr2->bits[0]);
427       else
428         bi->actual = bi->ptr1->bits[0];
429     }
430
431   return bmp_iter_and_not_next_1 (bi);
432 }
433
434 /* Moves the iterator BI to the next bit of difference of bitmaps and returns
435    the bit if available.  */
436
437 static inline unsigned
438 bmp_iter_and_not_next (bitmap_iterator *bi)
439 {
440   bi->bit++;
441   bi->actual >>= 1;
442   return bmp_iter_and_not_next_1 (bi);
443 }
444
445 /* Loop over all bits in BMP1 and BMP2, starting with MIN, setting
446    BITNUM to the bit number for all bits that are set in the first bitmap
447    and not set in the second.  ITER is a bitmap iterator.  */
448
449 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BMP1, BMP2, MIN, BITNUM, ITER)   \
450   for ((BITNUM) = bmp_iter_and_not_init (&(ITER), (BMP1), (BMP2), (MIN)); \
451        !bmp_iter_end_p (&(ITER));                                               \
452        (BITNUM) = bmp_iter_and_not_next (&(ITER)))
453
454 /* Moves the iterator BI to the first set bit on or after the current
455    position in intersection of bitmaps and returns the bit if available.  */
456
457 static inline unsigned
458 bmp_iter_and_next_1 (bitmap_iterator *bi)
459 {
460   if (bi->actual)
461     return bmp_iter_common_next_1 (bi);
462
463   bi->word++;
464   bi->word_bit += BITMAP_WORD_BITS;
465
466   while (1)
467     {
468       for (;
469            bi->word < BITMAP_ELEMENT_WORDS;
470            bi->word++, bi->word_bit += BITMAP_WORD_BITS)
471         {
472           bi->actual = (bi->ptr1->bits[bi->word]
473                         & bi->ptr2->bits[bi->word]);
474           if (bi->actual)
475             {
476               bi->bit = bi->word_bit;
477               return bmp_iter_common_next_1 (bi);
478             }
479         }
480
481       do
482         {
483           bi->ptr1 = bi->ptr1->next;
484           if (!bi->ptr1)
485             return 0;
486
487           while (bi->ptr2->indx < bi->ptr1->indx)
488             {
489               bi->ptr2 = bi->ptr2->next;
490               if (!bi->ptr2)
491                 {
492                   bi->ptr1 = NULL;
493                   return 0;
494                 }
495             }
496         }
497       while (bi->ptr1->indx != bi->ptr2->indx);
498
499       bi->word = 0;
500       bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
501     }
502 }
503
504 /* Initializes a bitmap iterator BI for looping over bits of bitmap
505    BMP1 & BMP2, starting with bit MIN.  Returns the first bit of
506    BMP1 & BMP2 greater or equal to MIN if there is any.  */
507
508 static inline unsigned
509 bmp_iter_and_init (bitmap_iterator *bi, bitmap bmp1, bitmap bmp2,
510                        unsigned min)
511 {
512   unsigned indx = min / BITMAP_ELEMENT_ALL_BITS;
513
514   for (bi->ptr1 = bmp1->first;
515        bi->ptr1 && bi->ptr1->indx < indx;
516        bi->ptr1 = bi->ptr1->next)
517     continue;
518
519   if (!bi->ptr1)
520     goto empty;
521
522   bi->ptr2 = bmp2->first;
523   if (!bi->ptr2)
524     goto empty;
525
526   while (1)
527     {
528       while (bi->ptr2->indx < bi->ptr1->indx)
529         {
530           bi->ptr2 = bi->ptr2->next;
531           if (!bi->ptr2)
532             goto empty;
533         }
534
535       if (bi->ptr1->indx == bi->ptr2->indx)
536         break;
537
538       bi->ptr1 = bi->ptr1->next;
539       if (!bi->ptr1)
540         goto empty;
541     }
542
543   if (bi->ptr1->indx == indx)
544     {
545       unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx;
546       unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS;
547       unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS;
548
549       bi->word = word_in_elt;
550       bi->word_bit = min - bit_in_word;
551       bi->bit = min;
552
553       bi->actual = (bi->ptr1->bits[word_in_elt]
554                     & bi->ptr2->bits[word_in_elt]) >> bit_in_word;
555     }
556   else
557     {
558       bi->word = 0;
559       bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
560       bi->word_bit = bi->bit;
561
562       bi->actual = (bi->ptr1->bits[0] & bi->ptr2->bits[0]);
563     }
564
565   return bmp_iter_and_next_1 (bi);
566
567 empty:
568   /* To avoid warnings.  */
569   bi->word = 0;
570   bi->bit = 0;
571   bi->word_bit = 0;
572   bi->actual = 0;
573   bi->ptr1 = NULL;
574   bi->ptr2 = NULL;
575   return 0;
576 }
577
578 /* Moves the iterator BI to the next bit of intersection of bitmaps and returns
579    the bit if available.  */
580
581 static inline unsigned
582 bmp_iter_and_next (bitmap_iterator *bi)
583 {
584   bi->bit++;
585   bi->actual >>= 1;
586   return bmp_iter_and_next_1 (bi);
587 }
588
589 /* Loop over all bits in BMP1 and BMP2, starting with MIN, setting
590    BITNUM to the bit number for all bits that are set in both bitmaps.
591    ITER is a bitmap iterator.  */
592
593 #define EXECUTE_IF_AND_IN_BITMAP(BMP1, BMP2, MIN, BITNUM, ITER)         \
594   for ((BITNUM) = bmp_iter_and_init (&(ITER), (BMP1), (BMP2), (MIN));   \
595        !bmp_iter_end_p (&(ITER));                                               \
596        (BITNUM) = bmp_iter_and_next (&(ITER)))
597
598 #endif /* GCC_BITMAP_H */