source: trunk/third/gcc/bitmap.h @ 11288

Revision 11288, 10.2 KB checked in by ghudson, 26 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r11287, which included commits to RCS files with non-trunk default branches.
Line 
1/* Functions to support general ended bitmaps.
2   Copyright (C) 1997 Free Software Foundation, Inc.
3
4This file is part of GNU CC.
5
6GNU CC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 2, or (at your option)
9any later version.
10
11GNU CC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with GNU CC; see the file COPYING.  If not, write to
18the Free Software Foundation, 59 Temple Place - Suite 330,
19Boston, MA 02111-1307, USA.  */
20
21/* Number of words to use for each element in the linked list.  */
22
23#ifndef BITMAP_ELEMENT_WORDS
24#define BITMAP_ELEMENT_WORDS 2
25#endif
26
27/* Number of bits in each actual element of a bitmap.  We get slightly better
28   code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if
29   bits is unsigned, assuming it is a power of 2.  */
30
31#define BITMAP_ELEMENT_ALL_BITS \
32  ((unsigned) (BITMAP_ELEMENT_WORDS * HOST_BITS_PER_WIDE_INT))
33
34/* Bitmap set element.  We use a linked list to hold only the bits that
35   are set.  This allows for use to grow the bitset dynamically without
36   having to realloc and copy a giant bit array.  The `prev' field is
37   undefined for an element on the free list.  */
38
39typedef struct bitmap_element_def
40{
41  struct bitmap_element_def *next;              /* Next element. */
42  struct bitmap_element_def *prev;              /* Previous element. */
43  unsigned int indx;                    /* regno/BITMAP_ELEMENT_ALL_BITS. */
44  unsigned HOST_WIDE_INT bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */
45} bitmap_element;
46
47/* Head of bitmap linked list.  */
48typedef struct bitmap_head_def {
49  bitmap_element *first;        /* First element in linked list. */
50  bitmap_element *current;      /* Last element looked at. */
51  int indx;                     /* Index of last element looked at. */
52} bitmap_head, *bitmap;
53
54/* Enumeration giving the various operations we support.  */
55enum bitmap_bits {
56  BITMAP_AND,                   /* TO = FROM1 & FROM2 */
57  BITMAP_AND_COMPL,             /* TO = FROM1 & ~ FROM2 */
58  BITMAP_IOR                    /* TO = FROM1 | FROM2 */
59};
60
61/* Global data */
62extern bitmap_element *bitmap_free;     /* Freelist of bitmap elements */
63extern bitmap_element bitmap_zero;      /* Zero bitmap element */
64
65/* Clear a bitmap by freeing up the linked list.  */
66extern void bitmap_clear PROTO((bitmap));
67
68/* Copy a bitmap to another bitmap. */
69extern void bitmap_copy PROTO((bitmap, bitmap));
70
71/* Perform an operation on two bitmaps, yielding a third.  */
72extern void bitmap_operation PROTO((bitmap, bitmap, bitmap, enum bitmap_bits));
73
74/* `or' into one bitmap the `and' of a second bitmap witih the complement
75   of a third.  */
76extern void bitmap_ior_and_compl PROTO((bitmap, bitmap, bitmap));
77
78/* Clear a single register in a register set.  */
79extern void bitmap_clear_bit PROTO((bitmap, int));
80
81/* Set a single register in a register set.  */
82extern void bitmap_set_bit PROTO((bitmap, int));
83
84/* Return true if a register is set in a register set.  */
85extern int bitmap_bit_p PROTO((bitmap, int));
86
87/* Debug functions to print a bitmap linked list.  */
88extern void bitmap_debug PROTO((bitmap));
89extern void bitmap_debug_file PROTO((FILE *, bitmap));
90
91/* Print a bitmap */
92extern void bitmap_print PROTO((FILE *, bitmap, char *, char *));
93
94/* Initialize a bitmap header.  */
95extern bitmap bitmap_initialize PROTO((bitmap));
96
97/* Release all memory held by bitmaps.  */
98extern void bitmap_release_memory PROTO((void));
99
100/* Allocate a bitmap with oballoc.  */
101#define BITMAP_OBSTACK_ALLOC(OBSTACK)                           \
102  bitmap_initialize ((bitmap) obstack_alloc (OBSTACK, sizeof (bitmap_head)))
103
104/* Allocate a bitmap with alloca.  */
105#define BITMAP_ALLOCA()                                         \
106  bitmap_initialize ((bitmap) alloca (sizeof (bitmap_head)))
107
108/* Do any cleanup needed on a bitmap when it is no longer used.  */
109#define BITMAP_FREE(BITMAP)                                     \
110do {                            \
111  if (BITMAP)                   \
112    {                           \
113      bitmap_clear (BITMAP);    \
114      (BITMAP) = 0;             \
115    }                                                                   \
116} while (0)
117
118/* Do any one-time initializations needed for bitmaps.  */
119#define BITMAP_INIT_ONCE()
120
121/* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the
122   bit number and executing CODE for all bits that are set. */
123
124#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE)             \
125do {                                                                    \
126  bitmap_element *ptr_ = (BITMAP)->first;                               \
127  unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
128  unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
129  unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
130                        % BITMAP_ELEMENT_WORDS);                        \
131                                                                        \
132                                                                        \
133  /* Find the block the minimum bit is in.  */                          \
134  while (ptr_ != 0 && ptr_->indx < indx_)                               \
135    ptr_ = ptr_->next;                                                  \
136                                                                        \
137  if (ptr_ != 0 && ptr_->indx != indx_)                                 \
138    {                                                                   \
139      bit_num_ = 0;                                                     \
140      word_num_ = 0;                                                    \
141    }                                                                   \
142                                                                        \
143  for (; ptr_ != 0; ptr_ = ptr_->next)                                  \
144    {                                                                   \
145      for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
146        {                                                               \
147          unsigned HOST_WIDE_INT word_ = ptr_->bits[word_num_];         \
148                                                                        \
149          if (word_ != 0)                                               \
150            {                                                           \
151              for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
152                {                                                       \
153                  unsigned HOST_WIDE_INT mask_                          \
154                    = ((unsigned HOST_WIDE_INT) 1) << bit_num_;         \
155                                                                        \
156                  if ((word_ & mask_) != 0)                             \
157                    {                                                   \
158                      word_ &= ~ mask_;                                 \
159                      (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS  \
160                                  + word_num_ * HOST_BITS_PER_WIDE_INT  \
161                                  + bit_num_);                          \
162                      CODE;                                             \
163                                                                        \
164                      if (word_ == 0)                                   \
165                        break;                                          \
166                    }                                                   \
167                }                                                       \
168            }                                                           \
169                                                                        \
170          bit_num_ = 0;                                                 \
171        }                                                               \
172                                                                        \
173      word_num_ = 0;                                                    \
174    }                                                                   \
175} while (0)
176
177/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
178   BITNUM to the bit number and executing CODE for all bits that are set in
179   the first bitmap and not set in the second. */
180
181#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \
182do {                                                                    \
183  bitmap_element *ptr1_ = (BITMAP1)->first;                             \
184  bitmap_element *ptr2_ = (BITMAP2)->first;                             \
185  unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
186  unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
187  unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
188                        % BITMAP_ELEMENT_WORDS);                        \
189                                                                        \
190  /* Find the block the minimum bit is in in the first bitmap.  */      \
191  while (ptr1_ != 0 && ptr1_->indx < indx_)                             \
192    ptr1_ = ptr1_->next;                                                \
193                                                                        \
194  if (ptr1_ != 0 && ptr1_->indx != indx_)                               \
195    {                                                                   \
196      bit_num_ = 0;                                                     \
197      word_num_ = 0;                                                    \
198    }                                                                   \
199                                                                        \
200  for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)                              \
201    {                                                                   \
202      /* Advance BITMAP2 to the equivalent link, using an all           \
203         zero element if an equivalent link doesn't exist.  */          \
204      bitmap_element *tmp2_;                                            \
205                                                                        \
206      while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)                   \
207        ptr2_ = ptr2_->next;                                            \
208                                                                        \
209      tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx)               \
210               ? ptr2_ : &bitmap_zero);                                 \
211                                                                        \
212      for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
213        {                                                               \
214          unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]        \
215                                          & ~ tmp2_->bits[word_num_]);  \
216          if (word_ != 0)                                               \
217            {                                                           \
218              for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
219                {                                                       \
220                  unsigned HOST_WIDE_INT mask_                          \
221                    = ((unsigned HOST_WIDE_INT)1) << bit_num_;          \
222                                                                        \
223                  if ((word_ & mask_) != 0)                             \
224                    {                                                   \
225                      word_ &= ~ mask_;                                 \
226                      (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
227                                  + word_num_ * HOST_BITS_PER_WIDE_INT  \
228                                  + bit_num_);                          \
229                                                                        \
230                      CODE;                                             \
231                      if (word_ == 0)                                   \
232                        break;                                          \
233                    }                                                   \
234                }                                                       \
235            }                                                           \
236                                                                        \
237          bit_num_ = 0;                                                 \
238        }                                                               \
239                                                                        \
240      word_num_ = 0;                                                    \
241    }                                                                   \
242} while (0)
243
244/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
245   BITNUM to the bit number and executing CODE for all bits that are set in
246   the both bitmaps. */
247
248#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE)   \
249do {                                                                    \
250  bitmap_element *ptr1_ = (BITMAP1)->first;                             \
251  bitmap_element *ptr2_ = (BITMAP2)->first;                             \
252  unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
253  unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
254  unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
255                        % BITMAP_ELEMENT_WORDS);                        \
256                                                                        \
257  /* Find the block the minimum bit is in in the first bitmap.  */      \
258  while (ptr1_ != 0 && ptr1_->indx < indx_)                             \
259    ptr1_ = ptr1_->next;                                                \
260                                                                        \
261  if (ptr1_ != 0 && ptr1_->indx != indx_)                               \
262    {                                                                   \
263      bit_num_ = 0;                                                     \
264      word_num_ = 0;                                                    \
265    }                                                                   \
266                                                                        \
267  for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)                              \
268    {                                                                   \
269      /* Advance BITMAP2 to the equivalent link */                      \
270      while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)                   \
271        ptr2_ = ptr2_->next;                                            \
272                                                                        \
273      if (ptr2_ == 0)                                                   \
274        {                                                               \
275          /* If there are no more elements in BITMAP2, exit loop now.*/ \
276          ptr1_ = (bitmap_element *)0;                                  \
277          break;                                                        \
278        }                                                               \
279      else if (ptr2_->indx > ptr1_->indx)                               \
280        {                                                               \
281          bit_num_ = word_num_ = 0;                                     \
282          continue;                                                     \
283        }                                                               \
284                                                                        \
285      for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
286        {                                                               \
287          unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]        \
288                                          & ptr2_->bits[word_num_]);    \
289          if (word_ != 0)                                               \
290            {                                                           \
291              for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
292                {                                                       \
293                  unsigned HOST_WIDE_INT mask_                          \
294                    = ((unsigned HOST_WIDE_INT)1) << bit_num_;          \
295                                                                        \
296                  if ((word_ & mask_) != 0)                             \
297                    {                                                   \
298                      word_ &= ~ mask_;                                 \
299                      (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
300                                  + word_num_ * HOST_BITS_PER_WIDE_INT  \
301                                  + bit_num_);                          \
302                                                                        \
303                      CODE;                                             \
304                      if (word_ == 0)                                   \
305                        break;                                          \
306                    }                                                   \
307                }                                                       \
308            }                                                           \
309                                                                        \
310          bit_num_ = 0;                                                 \
311        }                                                               \
312                                                                        \
313      word_num_ = 0;                                                    \
314    }                                                                   \
315} while (0)
Note: See TracBrowser for help on using the repository browser.