OSDN Git Service

9f89da8b39cbdf0caed910049746ea24e611c8ad
[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 bool bitmap_equal_p (bitmap, bitmap);
89
90 /* True if the bitmaps intersect (their AND is non-empty).  */
91 extern bool bitmap_intersect_p (bitmap, bitmap);
92
93 /* True if the complement of the second intersects the first (their
94    AND_COMPL is non-empty).  */
95 extern bool bitmap_intersect_compl_p (bitmap, bitmap);
96
97 /* True if MAP is an empty bitmap.  */
98 #define bitmap_empty_p(MAP) (!(MAP)->first)
99
100 /* Perform an operation on two bitmaps, yielding a third.  */
101 extern int bitmap_operation (bitmap, bitmap, bitmap, enum bitmap_bits);
102
103 #define bitmap_and(DST,A,B) (void)bitmap_operation (DST,A,B,BITMAP_AND)
104 #define bitmap_and_into(DST_SRC,B) (void)bitmap_operation (DST_SRC,DST_SRC,B,BITMAP_AND)
105 #define bitmap_and_compl(DST,A,B) (void)bitmap_operation (DST,A,B,BITMAP_AND_COMPL)
106 #define bitmap_and_compl_into(DST_SRC,B) (void)bitmap_operation (DST_SRC,DST_SRC,B,BITMAP_AND_COMPL)
107 #define bitmap_ior(DST,A,B) (void)bitmap_operation (DST,A,B,BITMAP_IOR)
108 #define bitmap_ior_into(DST_SRC,B) (void)bitmap_operation (DST_SRC,DST_SRC,B,BITMAP_IOR)
109 #define bitmap_ior_compl(DST,A,B) (void)bitmap_operation (DST,A,Br,BITMAP_IOR_COMPL)
110 #define bitmap_xor(DST,A,B) (void)bitmap_operation (DST,A,B,BITMAP_XOR)
111 #define bitmap_xor_into(DST_SRC,B) (void)bitmap_operation (DST_SRC,DST_SRC,B,BITMAP_XOR)
112
113 /* `or' into one bitmap the `and' of a second bitmap witih the complement
114    of a third. Return nonzero if the bitmap changes.  */
115 extern bool bitmap_ior_and_compl_into (bitmap, bitmap, bitmap);
116 extern bool bitmap_ior_and_compl (bitmap, bitmap, bitmap, bitmap);
117
118 /* Clear a single register in a register set.  */
119 extern void bitmap_clear_bit (bitmap, int);
120
121 /* Set a single register in a register set.  */
122 extern void bitmap_set_bit (bitmap, int);
123
124 /* Return true if a register is set in a register set.  */
125 extern int bitmap_bit_p (bitmap, int);
126
127 /* Debug functions to print a bitmap linked list.  */
128 extern void debug_bitmap (bitmap);
129 extern void debug_bitmap_file (FILE *, bitmap);
130
131 /* Print a bitmap.  */
132 extern void bitmap_print (FILE *, bitmap, const char *, const char *);
133
134 /* Initialize a bitmap header.  If HEAD is NULL, a new header will be
135    allocated.  USING_OBSTACK indicates how elements should be allocated.  */
136 extern bitmap bitmap_initialize (bitmap head, int using_obstack);
137
138 /* Release all memory used by the bitmap obstack.  */
139 extern void bitmap_release_memory (void);
140
141 /* A few compatibility/functions macros for compatibility with sbitmaps */
142 #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
143 #define bitmap_zero(a) bitmap_clear (a)
144 extern int bitmap_first_set_bit (bitmap);
145 extern int bitmap_last_set_bit (bitmap);
146
147 /* Allocate a bitmap with oballoc.  */
148 #define BITMAP_OBSTACK_ALLOC(OBSTACK)                           \
149   bitmap_initialize (obstack_alloc (OBSTACK, sizeof (bitmap_head)), 1)
150
151 /* Allocate a bitmap with ggc_alloc.  */
152 #define BITMAP_GGC_ALLOC()                      \
153   bitmap_initialize (NULL, 0)
154
155 /* Allocate a bitmap with xmalloc.  */
156 #define BITMAP_XMALLOC()                                        \
157   bitmap_initialize (xmalloc (sizeof (bitmap_head)), 1)
158
159 /* Do any cleanup needed on a bitmap when it is no longer used.  */
160 #define BITMAP_FREE(BITMAP)                     \
161 do {                                            \
162   if (BITMAP)                                   \
163     {                                           \
164       bitmap_clear (BITMAP);                    \
165       (BITMAP) = 0;                             \
166     }                                           \
167 } while (0)
168
169 /* Do any cleanup needed on an xmalloced bitmap when it is no longer used.  */
170 #define BITMAP_XFREE(BITMAP)                    \
171 do {                                            \
172   if (BITMAP)                                   \
173     {                                           \
174       bitmap_clear (BITMAP);                    \
175       free (BITMAP);                            \
176       (BITMAP) = 0;                             \
177     }                                           \
178 } while (0)
179
180 /* Do any one-time initializations needed for bitmaps.  */
181 #define BITMAP_INIT_ONCE()
182
183 /* Iterator for bitmaps.  */
184
185 typedef struct
186 {
187   /* Actual elements in the bitmaps.  */
188   bitmap_element *ptr1, *ptr2;
189
190   /* Position of an actual word in the elements.  */
191   unsigned word;
192
193   /* Position of a bit corresponding to the start of word.  */
194   unsigned word_bit;
195
196   /* Position of the actual bit.  */
197   unsigned bit;
198
199   /* Contents of the actually processed word.  When finding next bit
200      it is shifted right, so that the actual bit is always the least
201      significant bit of ACTUAL.  */
202   BITMAP_WORD actual;
203 } bitmap_iterator;
204
205 /* Moves the iterator BI to the first set bit on or after the current
206    position in bitmap and returns the bit if available.  The bit is
207    found in ACTUAL field only.  */
208
209 static inline unsigned
210 bmp_iter_common_next_1 (bitmap_iterator *bi)
211 {
212   while (!(bi->actual & 1))
213     {
214       bi->actual >>= 1;
215       bi->bit++;
216     }
217
218   return bi->bit;
219 }
220
221 /* Moves the iterator BI to the first set bit on or after the current
222    position in bitmap and returns the bit if available.  */
223
224 static inline unsigned
225 bmp_iter_single_next_1 (bitmap_iterator *bi)
226 {
227   if (bi->actual)
228     return bmp_iter_common_next_1 (bi);
229
230   bi->word++;
231   bi->word_bit += BITMAP_WORD_BITS;
232
233   while (1)
234     {
235       for (;
236            bi->word < BITMAP_ELEMENT_WORDS;
237            bi->word++, bi->word_bit += BITMAP_WORD_BITS)
238         {
239           bi->actual = bi->ptr1->bits[bi->word];
240           if (bi->actual)
241             {
242               bi->bit = bi->word_bit;
243               return bmp_iter_common_next_1 (bi);
244             }
245         }
246
247       bi->ptr1 = bi->ptr1->next;
248       if (!bi->ptr1)
249         return 0;
250
251       bi->word = 0;
252       bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
253     }
254 }
255
256 /* Initializes a bitmap iterator BI for looping over bits of bitmap
257    BMP, starting with bit MIN.  Returns the first bit of BMP greater
258    or equal to MIN if there is any.  */
259
260 static inline unsigned
261 bmp_iter_single_init (bitmap_iterator *bi, bitmap bmp, unsigned min)
262 {
263   unsigned indx = min / BITMAP_ELEMENT_ALL_BITS;
264
265   for (bi->ptr1 = bmp->first;
266        bi->ptr1 && bi->ptr1->indx < indx;
267        bi->ptr1 = bi->ptr1->next)
268     continue;
269
270   if (!bi->ptr1)
271     {
272       /* To avoid warnings.  */
273       bi->word = 0;
274       bi->bit = 0;
275       bi->word_bit = 0;
276       bi->actual = 0;
277       bi->ptr2 = NULL;
278       return 0;
279     }
280
281   if (bi->ptr1->indx == indx)
282     {
283       unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx;
284       unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS;
285       unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS;
286
287       bi->word = word_in_elt;
288       bi->word_bit = min - bit_in_word;
289       bi->bit = min;
290       bi->actual = bi->ptr1->bits[word_in_elt] >> bit_in_word;
291     }
292   else
293     {
294       bi->word = 0;
295       bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
296       bi->word_bit = bi->bit;
297       bi->actual = bi->ptr1->bits[0];
298     }
299
300   return bmp_iter_single_next_1 (bi);
301 }
302
303 /* Returns true if all elements of the bitmap referred to by iterator BI
304    were processed.  */
305
306 static inline bool
307 bmp_iter_end_p (const bitmap_iterator *bi)
308 {
309   return bi->ptr1 == NULL;
310 }
311
312 /* Moves the iterator BI to the next bit of bitmap and returns the bit
313    if available.  */
314
315 static inline unsigned
316 bmp_iter_single_next (bitmap_iterator *bi)
317 {
318   bi->bit++;
319   bi->actual >>= 1;
320   return bmp_iter_single_next_1 (bi);
321 }
322
323 /* Loop over all bits in BITMAP, starting with MIN and setting BITNUM to
324    the bit number.  ITER is a bitmap iterator.  */
325
326 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)             \
327   for ((BITNUM) = bmp_iter_single_init (&(ITER), (BITMAP), (MIN));      \
328        !bmp_iter_end_p (&(ITER));                                       \
329        (BITNUM) = bmp_iter_single_next (&(ITER)))
330
331 /* Moves the iterator BI to the first set bit on or after the current
332    position in difference of bitmaps and returns the bit if available.  */
333
334 static inline unsigned
335 bmp_iter_and_not_next_1 (bitmap_iterator *bi)
336 {
337   if (bi->actual)
338     return bmp_iter_common_next_1 (bi);
339
340   bi->word++;
341   bi->word_bit += BITMAP_WORD_BITS;
342
343   while (1)
344     {
345       bitmap_element *snd;
346
347       if (bi->ptr2 && bi->ptr2->indx == bi->ptr1->indx)
348         snd = bi->ptr2;
349       else
350         snd = &bitmap_zero_bits;
351
352       for (;
353            bi->word < BITMAP_ELEMENT_WORDS;
354            bi->word++, bi->word_bit += BITMAP_WORD_BITS)
355         {
356           bi->actual = (bi->ptr1->bits[bi->word]
357                         & ~snd->bits[bi->word]);
358           if (bi->actual)
359             {
360               bi->bit = bi->word_bit;
361               return bmp_iter_common_next_1 (bi);
362             }
363         }
364
365       bi->ptr1 = bi->ptr1->next;
366       if (!bi->ptr1)
367         return 0;
368
369       while (bi->ptr2
370              && bi->ptr2->indx < bi->ptr1->indx)
371         bi->ptr2 = bi->ptr2->next;
372
373       bi->word = 0;
374       bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
375     }
376 }
377
378 /* Initializes a bitmap iterator BI for looping over bits of bitmap
379    BMP1 &~ BMP2, starting with bit MIN.  Returns the first bit of
380    BMP1 &~ BMP2 greater or equal to MIN if there is any.  */
381
382 static inline unsigned
383 bmp_iter_and_not_init (bitmap_iterator *bi, bitmap bmp1, bitmap bmp2,
384                        unsigned min)
385 {
386   unsigned indx = min / BITMAP_ELEMENT_ALL_BITS;
387
388   for (bi->ptr1 = bmp1->first;
389        bi->ptr1 && bi->ptr1->indx < indx;
390        bi->ptr1 = bi->ptr1->next)
391     continue;
392
393   if (!bi->ptr1)
394     {
395       /* To avoid warnings.  */
396       bi->word = 0;
397       bi->bit = 0;
398       bi->word_bit = 0;
399       bi->actual = 0;
400       bi->ptr2 = NULL;
401       return 0;
402     }
403
404   for (bi->ptr2 = bmp2->first;
405        bi->ptr2 && bi->ptr2->indx < bi->ptr1->indx;
406        bi->ptr2 = bi->ptr2->next)
407     continue;
408
409   if (bi->ptr1->indx == indx)
410     {
411       unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx;
412       unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS;
413       unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS;
414
415       bi->word = word_in_elt;
416       bi->word_bit = min - bit_in_word;
417       bi->bit = min;
418
419       if (bi->ptr2 && bi->ptr2->indx == indx)
420         bi->actual = (bi->ptr1->bits[word_in_elt]
421                       & ~bi->ptr2->bits[word_in_elt]) >> bit_in_word;
422       else
423        bi->actual = bi->ptr1->bits[word_in_elt] >> bit_in_word;
424     }
425   else
426     {
427       bi->word = 0;
428       bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
429       bi->word_bit = bi->bit;
430
431       if (bi->ptr2 && bi->ptr2->indx == bi->ptr1->indx)
432         bi->actual = (bi->ptr1->bits[0] & ~bi->ptr2->bits[0]);
433       else
434         bi->actual = bi->ptr1->bits[0];
435     }
436
437   return bmp_iter_and_not_next_1 (bi);
438 }
439
440 /* Moves the iterator BI to the next bit of difference of bitmaps and returns
441    the bit if available.  */
442
443 static inline unsigned
444 bmp_iter_and_not_next (bitmap_iterator *bi)
445 {
446   bi->bit++;
447   bi->actual >>= 1;
448   return bmp_iter_and_not_next_1 (bi);
449 }
450
451 /* Loop over all bits in BMP1 and BMP2, starting with MIN, setting
452    BITNUM to the bit number for all bits that are set in the first bitmap
453    and not set in the second.  ITER is a bitmap iterator.  */
454
455 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BMP1, BMP2, MIN, BITNUM, ITER)   \
456   for ((BITNUM) = bmp_iter_and_not_init (&(ITER), (BMP1), (BMP2), (MIN)); \
457        !bmp_iter_end_p (&(ITER));                                               \
458        (BITNUM) = bmp_iter_and_not_next (&(ITER)))
459
460 /* Moves the iterator BI to the first set bit on or after the current
461    position in intersection of bitmaps and returns the bit if available.  */
462
463 static inline unsigned
464 bmp_iter_and_next_1 (bitmap_iterator *bi)
465 {
466   if (bi->actual)
467     return bmp_iter_common_next_1 (bi);
468
469   bi->word++;
470   bi->word_bit += BITMAP_WORD_BITS;
471
472   while (1)
473     {
474       for (;
475            bi->word < BITMAP_ELEMENT_WORDS;
476            bi->word++, bi->word_bit += BITMAP_WORD_BITS)
477         {
478           bi->actual = (bi->ptr1->bits[bi->word]
479                         & bi->ptr2->bits[bi->word]);
480           if (bi->actual)
481             {
482               bi->bit = bi->word_bit;
483               return bmp_iter_common_next_1 (bi);
484             }
485         }
486
487       do
488         {
489           bi->ptr1 = bi->ptr1->next;
490           if (!bi->ptr1)
491             return 0;
492
493           while (bi->ptr2->indx < bi->ptr1->indx)
494             {
495               bi->ptr2 = bi->ptr2->next;
496               if (!bi->ptr2)
497                 {
498                   bi->ptr1 = NULL;
499                   return 0;
500                 }
501             }
502         }
503       while (bi->ptr1->indx != bi->ptr2->indx);
504
505       bi->word = 0;
506       bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
507     }
508 }
509
510 /* Initializes a bitmap iterator BI for looping over bits of bitmap
511    BMP1 & BMP2, starting with bit MIN.  Returns the first bit of
512    BMP1 & BMP2 greater or equal to MIN if there is any.  */
513
514 static inline unsigned
515 bmp_iter_and_init (bitmap_iterator *bi, bitmap bmp1, bitmap bmp2,
516                        unsigned min)
517 {
518   unsigned indx = min / BITMAP_ELEMENT_ALL_BITS;
519
520   for (bi->ptr1 = bmp1->first;
521        bi->ptr1 && bi->ptr1->indx < indx;
522        bi->ptr1 = bi->ptr1->next)
523     continue;
524
525   if (!bi->ptr1)
526     goto empty;
527
528   bi->ptr2 = bmp2->first;
529   if (!bi->ptr2)
530     goto empty;
531
532   while (1)
533     {
534       while (bi->ptr2->indx < bi->ptr1->indx)
535         {
536           bi->ptr2 = bi->ptr2->next;
537           if (!bi->ptr2)
538             goto empty;
539         }
540
541       if (bi->ptr1->indx == bi->ptr2->indx)
542         break;
543
544       bi->ptr1 = bi->ptr1->next;
545       if (!bi->ptr1)
546         goto empty;
547     }
548
549   if (bi->ptr1->indx == indx)
550     {
551       unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx;
552       unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS;
553       unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS;
554
555       bi->word = word_in_elt;
556       bi->word_bit = min - bit_in_word;
557       bi->bit = min;
558
559       bi->actual = (bi->ptr1->bits[word_in_elt]
560                     & bi->ptr2->bits[word_in_elt]) >> bit_in_word;
561     }
562   else
563     {
564       bi->word = 0;
565       bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
566       bi->word_bit = bi->bit;
567
568       bi->actual = (bi->ptr1->bits[0] & bi->ptr2->bits[0]);
569     }
570
571   return bmp_iter_and_next_1 (bi);
572
573 empty:
574   /* To avoid warnings.  */
575   bi->word = 0;
576   bi->bit = 0;
577   bi->word_bit = 0;
578   bi->actual = 0;
579   bi->ptr1 = NULL;
580   bi->ptr2 = NULL;
581   return 0;
582 }
583
584 /* Moves the iterator BI to the next bit of intersection of bitmaps and returns
585    the bit if available.  */
586
587 static inline unsigned
588 bmp_iter_and_next (bitmap_iterator *bi)
589 {
590   bi->bit++;
591   bi->actual >>= 1;
592   return bmp_iter_and_next_1 (bi);
593 }
594
595 /* Loop over all bits in BMP1 and BMP2, starting with MIN, setting
596    BITNUM to the bit number for all bits that are set in both bitmaps.
597    ITER is a bitmap iterator.  */
598
599 #define EXECUTE_IF_AND_IN_BITMAP(BMP1, BMP2, MIN, BITNUM, ITER)         \
600   for ((BITNUM) = bmp_iter_and_init (&(ITER), (BMP1), (BMP2), (MIN));   \
601        !bmp_iter_end_p (&(ITER));                                               \
602        (BITNUM) = bmp_iter_and_next (&(ITER)))
603
604 #endif /* GCC_BITMAP_H */