1*c87b03e5Sespie /* Functions to support general ended bitmaps.
2*c87b03e5Sespie Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003
3*c87b03e5Sespie Free Software Foundation, Inc.
4*c87b03e5Sespie
5*c87b03e5Sespie This file is part of GCC.
6*c87b03e5Sespie
7*c87b03e5Sespie GCC is free software; you can redistribute it and/or modify it under
8*c87b03e5Sespie the terms of the GNU General Public License as published by the Free
9*c87b03e5Sespie Software Foundation; either version 2, or (at your option) any later
10*c87b03e5Sespie version.
11*c87b03e5Sespie
12*c87b03e5Sespie GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13*c87b03e5Sespie WARRANTY; without even the implied warranty of MERCHANTABILITY or
14*c87b03e5Sespie FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15*c87b03e5Sespie for more details.
16*c87b03e5Sespie
17*c87b03e5Sespie You should have received a copy of the GNU General Public License
18*c87b03e5Sespie along with GCC; see the file COPYING. If not, write to the Free
19*c87b03e5Sespie Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20*c87b03e5Sespie 02111-1307, USA. */
21*c87b03e5Sespie
22*c87b03e5Sespie #include "config.h"
23*c87b03e5Sespie #include "system.h"
24*c87b03e5Sespie #include "rtl.h"
25*c87b03e5Sespie #include "flags.h"
26*c87b03e5Sespie #include "obstack.h"
27*c87b03e5Sespie #include "ggc.h"
28*c87b03e5Sespie #include "bitmap.h"
29*c87b03e5Sespie
30*c87b03e5Sespie /* Obstack to allocate bitmap elements from. */
31*c87b03e5Sespie static struct obstack bitmap_obstack;
32*c87b03e5Sespie static int bitmap_obstack_init = FALSE;
33*c87b03e5Sespie
34*c87b03e5Sespie #ifndef INLINE
35*c87b03e5Sespie #ifndef __GNUC__
36*c87b03e5Sespie #define INLINE
37*c87b03e5Sespie #else
38*c87b03e5Sespie #define INLINE __inline__
39*c87b03e5Sespie #endif
40*c87b03e5Sespie #endif
41*c87b03e5Sespie
42*c87b03e5Sespie /* Global data */
43*c87b03e5Sespie bitmap_element bitmap_zero_bits; /* An element of all zero bits. */
44*c87b03e5Sespie static bitmap_element *bitmap_free; /* Freelist of bitmap elements. */
45*c87b03e5Sespie static GTY((deletable (""))) bitmap_element *bitmap_ggc_free;
46*c87b03e5Sespie
47*c87b03e5Sespie static void bitmap_elem_to_freelist PARAMS ((bitmap, bitmap_element *));
48*c87b03e5Sespie static void bitmap_element_free PARAMS ((bitmap, bitmap_element *));
49*c87b03e5Sespie static bitmap_element *bitmap_element_allocate PARAMS ((bitmap));
50*c87b03e5Sespie static int bitmap_element_zerop PARAMS ((bitmap_element *));
51*c87b03e5Sespie static void bitmap_element_link PARAMS ((bitmap, bitmap_element *));
52*c87b03e5Sespie static bitmap_element *bitmap_find_bit PARAMS ((bitmap, unsigned int));
53*c87b03e5Sespie
54*c87b03e5Sespie /* Add ELEM to the appropriate freelist. */
55*c87b03e5Sespie static INLINE void
bitmap_elem_to_freelist(head,elt)56*c87b03e5Sespie bitmap_elem_to_freelist (head, elt)
57*c87b03e5Sespie bitmap head;
58*c87b03e5Sespie bitmap_element *elt;
59*c87b03e5Sespie {
60*c87b03e5Sespie if (head->using_obstack)
61*c87b03e5Sespie {
62*c87b03e5Sespie elt->next = bitmap_free;
63*c87b03e5Sespie bitmap_free = elt;
64*c87b03e5Sespie }
65*c87b03e5Sespie else
66*c87b03e5Sespie {
67*c87b03e5Sespie elt->next = bitmap_ggc_free;
68*c87b03e5Sespie bitmap_ggc_free = elt;
69*c87b03e5Sespie }
70*c87b03e5Sespie }
71*c87b03e5Sespie
72*c87b03e5Sespie /* Free a bitmap element. Since these are allocated off the
73*c87b03e5Sespie bitmap_obstack, "free" actually means "put onto the freelist". */
74*c87b03e5Sespie
75*c87b03e5Sespie static INLINE void
bitmap_element_free(head,elt)76*c87b03e5Sespie bitmap_element_free (head, elt)
77*c87b03e5Sespie bitmap head;
78*c87b03e5Sespie bitmap_element *elt;
79*c87b03e5Sespie {
80*c87b03e5Sespie bitmap_element *next = elt->next;
81*c87b03e5Sespie bitmap_element *prev = elt->prev;
82*c87b03e5Sespie
83*c87b03e5Sespie if (prev)
84*c87b03e5Sespie prev->next = next;
85*c87b03e5Sespie
86*c87b03e5Sespie if (next)
87*c87b03e5Sespie next->prev = prev;
88*c87b03e5Sespie
89*c87b03e5Sespie if (head->first == elt)
90*c87b03e5Sespie head->first = next;
91*c87b03e5Sespie
92*c87b03e5Sespie /* Since the first thing we try is to insert before current,
93*c87b03e5Sespie make current the next entry in preference to the previous. */
94*c87b03e5Sespie if (head->current == elt)
95*c87b03e5Sespie {
96*c87b03e5Sespie head->current = next != 0 ? next : prev;
97*c87b03e5Sespie if (head->current)
98*c87b03e5Sespie head->indx = head->current->indx;
99*c87b03e5Sespie }
100*c87b03e5Sespie bitmap_elem_to_freelist (head, elt);
101*c87b03e5Sespie }
102*c87b03e5Sespie
103*c87b03e5Sespie /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
104*c87b03e5Sespie
105*c87b03e5Sespie static INLINE bitmap_element *
bitmap_element_allocate(head)106*c87b03e5Sespie bitmap_element_allocate (head)
107*c87b03e5Sespie bitmap head;
108*c87b03e5Sespie {
109*c87b03e5Sespie bitmap_element *element;
110*c87b03e5Sespie
111*c87b03e5Sespie if (head->using_obstack)
112*c87b03e5Sespie {
113*c87b03e5Sespie if (bitmap_free != 0)
114*c87b03e5Sespie {
115*c87b03e5Sespie element = bitmap_free;
116*c87b03e5Sespie bitmap_free = element->next;
117*c87b03e5Sespie }
118*c87b03e5Sespie else
119*c87b03e5Sespie {
120*c87b03e5Sespie /* We can't use gcc_obstack_init to initialize the obstack since
121*c87b03e5Sespie print-rtl.c now calls bitmap functions, and bitmap is linked
122*c87b03e5Sespie into the gen* functions. */
123*c87b03e5Sespie if (!bitmap_obstack_init)
124*c87b03e5Sespie {
125*c87b03e5Sespie bitmap_obstack_init = TRUE;
126*c87b03e5Sespie
127*c87b03e5Sespie /* Let particular systems override the size of a chunk. */
128*c87b03e5Sespie #ifndef OBSTACK_CHUNK_SIZE
129*c87b03e5Sespie #define OBSTACK_CHUNK_SIZE 0
130*c87b03e5Sespie #endif
131*c87b03e5Sespie /* Let them override the alloc and free routines too. */
132*c87b03e5Sespie #ifndef OBSTACK_CHUNK_ALLOC
133*c87b03e5Sespie #define OBSTACK_CHUNK_ALLOC xmalloc
134*c87b03e5Sespie #endif
135*c87b03e5Sespie #ifndef OBSTACK_CHUNK_FREE
136*c87b03e5Sespie #define OBSTACK_CHUNK_FREE free
137*c87b03e5Sespie #endif
138*c87b03e5Sespie
139*c87b03e5Sespie #if !defined(__GNUC__) || (__GNUC__ < 2)
140*c87b03e5Sespie #define __alignof__(type) 0
141*c87b03e5Sespie #endif
142*c87b03e5Sespie
143*c87b03e5Sespie obstack_specify_allocation (&bitmap_obstack, OBSTACK_CHUNK_SIZE,
144*c87b03e5Sespie __alignof__ (bitmap_element),
145*c87b03e5Sespie (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC,
146*c87b03e5Sespie (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE);
147*c87b03e5Sespie }
148*c87b03e5Sespie
149*c87b03e5Sespie element = (bitmap_element *) obstack_alloc (&bitmap_obstack,
150*c87b03e5Sespie sizeof (bitmap_element));
151*c87b03e5Sespie }
152*c87b03e5Sespie }
153*c87b03e5Sespie else
154*c87b03e5Sespie {
155*c87b03e5Sespie if (bitmap_ggc_free != NULL)
156*c87b03e5Sespie {
157*c87b03e5Sespie element = bitmap_ggc_free;
158*c87b03e5Sespie bitmap_ggc_free = element->next;
159*c87b03e5Sespie }
160*c87b03e5Sespie else
161*c87b03e5Sespie element = ggc_alloc (sizeof (bitmap_element));
162*c87b03e5Sespie }
163*c87b03e5Sespie
164*c87b03e5Sespie memset (element->bits, 0, sizeof (element->bits));
165*c87b03e5Sespie
166*c87b03e5Sespie return element;
167*c87b03e5Sespie }
168*c87b03e5Sespie
169*c87b03e5Sespie /* Release any memory allocated by bitmaps. */
170*c87b03e5Sespie
171*c87b03e5Sespie void
bitmap_release_memory()172*c87b03e5Sespie bitmap_release_memory ()
173*c87b03e5Sespie {
174*c87b03e5Sespie bitmap_free = 0;
175*c87b03e5Sespie if (bitmap_obstack_init)
176*c87b03e5Sespie {
177*c87b03e5Sespie bitmap_obstack_init = FALSE;
178*c87b03e5Sespie obstack_free (&bitmap_obstack, NULL);
179*c87b03e5Sespie }
180*c87b03e5Sespie }
181*c87b03e5Sespie
182*c87b03e5Sespie /* Return nonzero if all bits in an element are zero. */
183*c87b03e5Sespie
184*c87b03e5Sespie static INLINE int
bitmap_element_zerop(element)185*c87b03e5Sespie bitmap_element_zerop (element)
186*c87b03e5Sespie bitmap_element *element;
187*c87b03e5Sespie {
188*c87b03e5Sespie #if BITMAP_ELEMENT_WORDS == 2
189*c87b03e5Sespie return (element->bits[0] | element->bits[1]) == 0;
190*c87b03e5Sespie #else
191*c87b03e5Sespie int i;
192*c87b03e5Sespie
193*c87b03e5Sespie for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
194*c87b03e5Sespie if (element->bits[i] != 0)
195*c87b03e5Sespie return 0;
196*c87b03e5Sespie
197*c87b03e5Sespie return 1;
198*c87b03e5Sespie #endif
199*c87b03e5Sespie }
200*c87b03e5Sespie
201*c87b03e5Sespie /* Link the bitmap element into the current bitmap linked list. */
202*c87b03e5Sespie
203*c87b03e5Sespie static INLINE void
bitmap_element_link(head,element)204*c87b03e5Sespie bitmap_element_link (head, element)
205*c87b03e5Sespie bitmap head;
206*c87b03e5Sespie bitmap_element *element;
207*c87b03e5Sespie {
208*c87b03e5Sespie unsigned int indx = element->indx;
209*c87b03e5Sespie bitmap_element *ptr;
210*c87b03e5Sespie
211*c87b03e5Sespie /* If this is the first and only element, set it in. */
212*c87b03e5Sespie if (head->first == 0)
213*c87b03e5Sespie {
214*c87b03e5Sespie element->next = element->prev = 0;
215*c87b03e5Sespie head->first = element;
216*c87b03e5Sespie }
217*c87b03e5Sespie
218*c87b03e5Sespie /* If this index is less than that of the current element, it goes someplace
219*c87b03e5Sespie before the current element. */
220*c87b03e5Sespie else if (indx < head->indx)
221*c87b03e5Sespie {
222*c87b03e5Sespie for (ptr = head->current;
223*c87b03e5Sespie ptr->prev != 0 && ptr->prev->indx > indx;
224*c87b03e5Sespie ptr = ptr->prev)
225*c87b03e5Sespie ;
226*c87b03e5Sespie
227*c87b03e5Sespie if (ptr->prev)
228*c87b03e5Sespie ptr->prev->next = element;
229*c87b03e5Sespie else
230*c87b03e5Sespie head->first = element;
231*c87b03e5Sespie
232*c87b03e5Sespie element->prev = ptr->prev;
233*c87b03e5Sespie element->next = ptr;
234*c87b03e5Sespie ptr->prev = element;
235*c87b03e5Sespie }
236*c87b03e5Sespie
237*c87b03e5Sespie /* Otherwise, it must go someplace after the current element. */
238*c87b03e5Sespie else
239*c87b03e5Sespie {
240*c87b03e5Sespie for (ptr = head->current;
241*c87b03e5Sespie ptr->next != 0 && ptr->next->indx < indx;
242*c87b03e5Sespie ptr = ptr->next)
243*c87b03e5Sespie ;
244*c87b03e5Sespie
245*c87b03e5Sespie if (ptr->next)
246*c87b03e5Sespie ptr->next->prev = element;
247*c87b03e5Sespie
248*c87b03e5Sespie element->next = ptr->next;
249*c87b03e5Sespie element->prev = ptr;
250*c87b03e5Sespie ptr->next = element;
251*c87b03e5Sespie }
252*c87b03e5Sespie
253*c87b03e5Sespie /* Set up so this is the first element searched. */
254*c87b03e5Sespie head->current = element;
255*c87b03e5Sespie head->indx = indx;
256*c87b03e5Sespie }
257*c87b03e5Sespie
258*c87b03e5Sespie /* Clear a bitmap by freeing the linked list. */
259*c87b03e5Sespie
260*c87b03e5Sespie INLINE void
bitmap_clear(head)261*c87b03e5Sespie bitmap_clear (head)
262*c87b03e5Sespie bitmap head;
263*c87b03e5Sespie {
264*c87b03e5Sespie bitmap_element *element, *next;
265*c87b03e5Sespie
266*c87b03e5Sespie for (element = head->first; element != 0; element = next)
267*c87b03e5Sespie {
268*c87b03e5Sespie next = element->next;
269*c87b03e5Sespie bitmap_elem_to_freelist (head, element);
270*c87b03e5Sespie }
271*c87b03e5Sespie
272*c87b03e5Sespie head->first = head->current = 0;
273*c87b03e5Sespie }
274*c87b03e5Sespie
275*c87b03e5Sespie /* Copy a bitmap to another bitmap. */
276*c87b03e5Sespie
277*c87b03e5Sespie void
bitmap_copy(to,from)278*c87b03e5Sespie bitmap_copy (to, from)
279*c87b03e5Sespie bitmap to;
280*c87b03e5Sespie bitmap from;
281*c87b03e5Sespie {
282*c87b03e5Sespie bitmap_element *from_ptr, *to_ptr = 0;
283*c87b03e5Sespie #if BITMAP_ELEMENT_WORDS != 2
284*c87b03e5Sespie int i;
285*c87b03e5Sespie #endif
286*c87b03e5Sespie
287*c87b03e5Sespie bitmap_clear (to);
288*c87b03e5Sespie
289*c87b03e5Sespie /* Copy elements in forward direction one at a time */
290*c87b03e5Sespie for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
291*c87b03e5Sespie {
292*c87b03e5Sespie bitmap_element *to_elt = bitmap_element_allocate (to);
293*c87b03e5Sespie
294*c87b03e5Sespie to_elt->indx = from_ptr->indx;
295*c87b03e5Sespie
296*c87b03e5Sespie #if BITMAP_ELEMENT_WORDS == 2
297*c87b03e5Sespie to_elt->bits[0] = from_ptr->bits[0];
298*c87b03e5Sespie to_elt->bits[1] = from_ptr->bits[1];
299*c87b03e5Sespie #else
300*c87b03e5Sespie for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
301*c87b03e5Sespie to_elt->bits[i] = from_ptr->bits[i];
302*c87b03e5Sespie #endif
303*c87b03e5Sespie
304*c87b03e5Sespie /* Here we have a special case of bitmap_element_link, for the case
305*c87b03e5Sespie where we know the links are being entered in sequence. */
306*c87b03e5Sespie if (to_ptr == 0)
307*c87b03e5Sespie {
308*c87b03e5Sespie to->first = to->current = to_elt;
309*c87b03e5Sespie to->indx = from_ptr->indx;
310*c87b03e5Sespie to_elt->next = to_elt->prev = 0;
311*c87b03e5Sespie }
312*c87b03e5Sespie else
313*c87b03e5Sespie {
314*c87b03e5Sespie to_elt->prev = to_ptr;
315*c87b03e5Sespie to_elt->next = 0;
316*c87b03e5Sespie to_ptr->next = to_elt;
317*c87b03e5Sespie }
318*c87b03e5Sespie
319*c87b03e5Sespie to_ptr = to_elt;
320*c87b03e5Sespie }
321*c87b03e5Sespie }
322*c87b03e5Sespie
323*c87b03e5Sespie /* Find a bitmap element that would hold a bitmap's bit.
324*c87b03e5Sespie Update the `current' field even if we can't find an element that
325*c87b03e5Sespie would hold the bitmap's bit to make eventual allocation
326*c87b03e5Sespie faster. */
327*c87b03e5Sespie
328*c87b03e5Sespie static INLINE bitmap_element *
bitmap_find_bit(head,bit)329*c87b03e5Sespie bitmap_find_bit (head, bit)
330*c87b03e5Sespie bitmap head;
331*c87b03e5Sespie unsigned int bit;
332*c87b03e5Sespie {
333*c87b03e5Sespie bitmap_element *element;
334*c87b03e5Sespie unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
335*c87b03e5Sespie
336*c87b03e5Sespie if (head->current == 0
337*c87b03e5Sespie || head->indx == indx)
338*c87b03e5Sespie return head->current;
339*c87b03e5Sespie
340*c87b03e5Sespie if (head->indx > indx)
341*c87b03e5Sespie for (element = head->current;
342*c87b03e5Sespie element->prev != 0 && element->indx > indx;
343*c87b03e5Sespie element = element->prev)
344*c87b03e5Sespie ;
345*c87b03e5Sespie
346*c87b03e5Sespie else
347*c87b03e5Sespie for (element = head->current;
348*c87b03e5Sespie element->next != 0 && element->indx < indx;
349*c87b03e5Sespie element = element->next)
350*c87b03e5Sespie ;
351*c87b03e5Sespie
352*c87b03e5Sespie /* `element' is the nearest to the one we want. If it's not the one we
353*c87b03e5Sespie want, the one we want doesn't exist. */
354*c87b03e5Sespie head->current = element;
355*c87b03e5Sespie head->indx = element->indx;
356*c87b03e5Sespie if (element != 0 && element->indx != indx)
357*c87b03e5Sespie element = 0;
358*c87b03e5Sespie
359*c87b03e5Sespie return element;
360*c87b03e5Sespie }
361*c87b03e5Sespie
362*c87b03e5Sespie /* Clear a single bit in a bitmap. */
363*c87b03e5Sespie
364*c87b03e5Sespie void
bitmap_clear_bit(head,bit)365*c87b03e5Sespie bitmap_clear_bit (head, bit)
366*c87b03e5Sespie bitmap head;
367*c87b03e5Sespie int bit;
368*c87b03e5Sespie {
369*c87b03e5Sespie bitmap_element *ptr = bitmap_find_bit (head, bit);
370*c87b03e5Sespie
371*c87b03e5Sespie if (ptr != 0)
372*c87b03e5Sespie {
373*c87b03e5Sespie unsigned bit_num = bit % BITMAP_WORD_BITS;
374*c87b03e5Sespie unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
375*c87b03e5Sespie ptr->bits[word_num] &= ~ (((BITMAP_WORD) 1) << bit_num);
376*c87b03e5Sespie
377*c87b03e5Sespie /* If we cleared the entire word, free up the element */
378*c87b03e5Sespie if (bitmap_element_zerop (ptr))
379*c87b03e5Sespie bitmap_element_free (head, ptr);
380*c87b03e5Sespie }
381*c87b03e5Sespie }
382*c87b03e5Sespie
383*c87b03e5Sespie /* Set a single bit in a bitmap. */
384*c87b03e5Sespie
385*c87b03e5Sespie void
bitmap_set_bit(head,bit)386*c87b03e5Sespie bitmap_set_bit (head, bit)
387*c87b03e5Sespie bitmap head;
388*c87b03e5Sespie int bit;
389*c87b03e5Sespie {
390*c87b03e5Sespie bitmap_element *ptr = bitmap_find_bit (head, bit);
391*c87b03e5Sespie unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
392*c87b03e5Sespie unsigned bit_num = bit % BITMAP_WORD_BITS;
393*c87b03e5Sespie BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
394*c87b03e5Sespie
395*c87b03e5Sespie if (ptr == 0)
396*c87b03e5Sespie {
397*c87b03e5Sespie ptr = bitmap_element_allocate (head);
398*c87b03e5Sespie ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
399*c87b03e5Sespie ptr->bits[word_num] = bit_val;
400*c87b03e5Sespie bitmap_element_link (head, ptr);
401*c87b03e5Sespie }
402*c87b03e5Sespie else
403*c87b03e5Sespie ptr->bits[word_num] |= bit_val;
404*c87b03e5Sespie }
405*c87b03e5Sespie
406*c87b03e5Sespie /* Return whether a bit is set within a bitmap. */
407*c87b03e5Sespie
408*c87b03e5Sespie int
bitmap_bit_p(head,bit)409*c87b03e5Sespie bitmap_bit_p (head, bit)
410*c87b03e5Sespie bitmap head;
411*c87b03e5Sespie int bit;
412*c87b03e5Sespie {
413*c87b03e5Sespie bitmap_element *ptr;
414*c87b03e5Sespie unsigned bit_num;
415*c87b03e5Sespie unsigned word_num;
416*c87b03e5Sespie
417*c87b03e5Sespie ptr = bitmap_find_bit (head, bit);
418*c87b03e5Sespie if (ptr == 0)
419*c87b03e5Sespie return 0;
420*c87b03e5Sespie
421*c87b03e5Sespie bit_num = bit % BITMAP_WORD_BITS;
422*c87b03e5Sespie word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
423*c87b03e5Sespie
424*c87b03e5Sespie return (ptr->bits[word_num] >> bit_num) & 1;
425*c87b03e5Sespie }
426*c87b03e5Sespie
427*c87b03e5Sespie /* Return the bit number of the first set bit in the bitmap, or -1
428*c87b03e5Sespie if the bitmap is empty. */
429*c87b03e5Sespie
430*c87b03e5Sespie int
bitmap_first_set_bit(a)431*c87b03e5Sespie bitmap_first_set_bit (a)
432*c87b03e5Sespie bitmap a;
433*c87b03e5Sespie {
434*c87b03e5Sespie bitmap_element *ptr = a->first;
435*c87b03e5Sespie BITMAP_WORD word;
436*c87b03e5Sespie unsigned word_num, bit_num;
437*c87b03e5Sespie
438*c87b03e5Sespie if (ptr == NULL)
439*c87b03e5Sespie return -1;
440*c87b03e5Sespie
441*c87b03e5Sespie #if BITMAP_ELEMENT_WORDS == 2
442*c87b03e5Sespie word_num = 0, word = ptr->bits[0];
443*c87b03e5Sespie if (word == 0)
444*c87b03e5Sespie word_num = 1, word = ptr->bits[1];
445*c87b03e5Sespie #else
446*c87b03e5Sespie for (word_num = 0; word_num < BITMAP_ELEMENT_WORDS; ++word_num)
447*c87b03e5Sespie if ((word = ptr->bits[word_num]) != 0)
448*c87b03e5Sespie break;
449*c87b03e5Sespie #endif
450*c87b03e5Sespie
451*c87b03e5Sespie /* Binary search for the first set bit. */
452*c87b03e5Sespie /* ??? It'd be nice to know if ffs or ffsl was available. */
453*c87b03e5Sespie
454*c87b03e5Sespie bit_num = 0;
455*c87b03e5Sespie word = word & -word;
456*c87b03e5Sespie
457*c87b03e5Sespie #if nBITMAP_WORD_BITS > 64
458*c87b03e5Sespie #error "Fill out the table."
459*c87b03e5Sespie #endif
460*c87b03e5Sespie #if nBITMAP_WORD_BITS > 32
461*c87b03e5Sespie if ((word & 0xffffffff) == 0)
462*c87b03e5Sespie word >>= 32, bit_num += 32;
463*c87b03e5Sespie #endif
464*c87b03e5Sespie if ((word & 0xffff) == 0)
465*c87b03e5Sespie word >>= 16, bit_num += 16;
466*c87b03e5Sespie if ((word & 0xff) == 0)
467*c87b03e5Sespie word >>= 8, bit_num += 8;
468*c87b03e5Sespie if (word & 0xf0)
469*c87b03e5Sespie bit_num += 4;
470*c87b03e5Sespie if (word & 0xcc)
471*c87b03e5Sespie bit_num += 2;
472*c87b03e5Sespie if (word & 0xaa)
473*c87b03e5Sespie bit_num += 1;
474*c87b03e5Sespie
475*c87b03e5Sespie return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
476*c87b03e5Sespie + word_num * BITMAP_WORD_BITS
477*c87b03e5Sespie + bit_num);
478*c87b03e5Sespie }
479*c87b03e5Sespie
480*c87b03e5Sespie /* Return the bit number of the last set bit in the bitmap, or -1
481*c87b03e5Sespie if the bitmap is empty. */
482*c87b03e5Sespie
483*c87b03e5Sespie int
bitmap_last_set_bit(a)484*c87b03e5Sespie bitmap_last_set_bit (a)
485*c87b03e5Sespie bitmap a;
486*c87b03e5Sespie {
487*c87b03e5Sespie bitmap_element *ptr = a->first;
488*c87b03e5Sespie BITMAP_WORD word;
489*c87b03e5Sespie unsigned word_num, bit_num;
490*c87b03e5Sespie
491*c87b03e5Sespie if (ptr == NULL)
492*c87b03e5Sespie return -1;
493*c87b03e5Sespie
494*c87b03e5Sespie while (ptr->next != NULL)
495*c87b03e5Sespie ptr = ptr->next;
496*c87b03e5Sespie
497*c87b03e5Sespie #if BITMAP_ELEMENT_WORDS == 2
498*c87b03e5Sespie word_num = 1, word = ptr->bits[1];
499*c87b03e5Sespie if (word == 0)
500*c87b03e5Sespie word_num = 0, word = ptr->bits[0];
501*c87b03e5Sespie #else
502*c87b03e5Sespie for (word_num = BITMAP_ELEMENT_WORDS; word_num-- > 0; )
503*c87b03e5Sespie if ((word = ptr->bits[word_num]) != 0)
504*c87b03e5Sespie break;
505*c87b03e5Sespie #endif
506*c87b03e5Sespie
507*c87b03e5Sespie /* Binary search for the last set bit. */
508*c87b03e5Sespie
509*c87b03e5Sespie bit_num = 0;
510*c87b03e5Sespie #if nBITMAP_WORD_BITS > 64
511*c87b03e5Sespie #error "Fill out the table."
512*c87b03e5Sespie #endif
513*c87b03e5Sespie #if nBITMAP_WORD_BITS > 32
514*c87b03e5Sespie if (word & ~(BITMAP_WORD)0xffffffff)
515*c87b03e5Sespie word >>= 32, bit_num += 32;
516*c87b03e5Sespie #endif
517*c87b03e5Sespie if (word & 0xffff0000)
518*c87b03e5Sespie word >>= 16, bit_num += 16;
519*c87b03e5Sespie if (word & 0xff00)
520*c87b03e5Sespie word >>= 8, bit_num += 8;
521*c87b03e5Sespie if (word & 0xf0)
522*c87b03e5Sespie word >>= 4, bit_num += 4;
523*c87b03e5Sespie if (word & 0xc)
524*c87b03e5Sespie word >>= 2, bit_num += 2;
525*c87b03e5Sespie if (word & 0x2)
526*c87b03e5Sespie bit_num += 1;
527*c87b03e5Sespie
528*c87b03e5Sespie return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
529*c87b03e5Sespie + word_num * BITMAP_WORD_BITS
530*c87b03e5Sespie + bit_num);
531*c87b03e5Sespie }
532*c87b03e5Sespie
533*c87b03e5Sespie /* Store in bitmap TO the result of combining bitmap FROM1 and FROM2 using
534*c87b03e5Sespie a specific bit manipulation. Return true if TO changes. */
535*c87b03e5Sespie
536*c87b03e5Sespie int
bitmap_operation(to,from1,from2,operation)537*c87b03e5Sespie bitmap_operation (to, from1, from2, operation)
538*c87b03e5Sespie bitmap to;
539*c87b03e5Sespie bitmap from1;
540*c87b03e5Sespie bitmap from2;
541*c87b03e5Sespie enum bitmap_bits operation;
542*c87b03e5Sespie {
543*c87b03e5Sespie #define HIGHEST_INDEX (unsigned int) ~0
544*c87b03e5Sespie
545*c87b03e5Sespie bitmap_element *from1_ptr = from1->first;
546*c87b03e5Sespie bitmap_element *from2_ptr = from2->first;
547*c87b03e5Sespie unsigned int indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX;
548*c87b03e5Sespie unsigned int indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX;
549*c87b03e5Sespie bitmap_element *to_ptr = to->first;
550*c87b03e5Sespie bitmap_element *from1_tmp;
551*c87b03e5Sespie bitmap_element *from2_tmp;
552*c87b03e5Sespie bitmap_element *to_tmp;
553*c87b03e5Sespie unsigned int indx;
554*c87b03e5Sespie int changed = 0;
555*c87b03e5Sespie
556*c87b03e5Sespie #if BITMAP_ELEMENT_WORDS == 2
557*c87b03e5Sespie #define DOIT(OP) \
558*c87b03e5Sespie do { \
559*c87b03e5Sespie BITMAP_WORD t0, t1, f10, f11, f20, f21; \
560*c87b03e5Sespie f10 = from1_tmp->bits[0]; \
561*c87b03e5Sespie f20 = from2_tmp->bits[0]; \
562*c87b03e5Sespie t0 = f10 OP f20; \
563*c87b03e5Sespie changed |= (t0 != to_tmp->bits[0]); \
564*c87b03e5Sespie f11 = from1_tmp->bits[1]; \
565*c87b03e5Sespie f21 = from2_tmp->bits[1]; \
566*c87b03e5Sespie t1 = f11 OP f21; \
567*c87b03e5Sespie changed |= (t1 != to_tmp->bits[1]); \
568*c87b03e5Sespie to_tmp->bits[0] = t0; \
569*c87b03e5Sespie to_tmp->bits[1] = t1; \
570*c87b03e5Sespie } while (0)
571*c87b03e5Sespie #else
572*c87b03e5Sespie #define DOIT(OP) \
573*c87b03e5Sespie do { \
574*c87b03e5Sespie BITMAP_WORD t, f1, f2; \
575*c87b03e5Sespie int i; \
576*c87b03e5Sespie for (i = 0; i < BITMAP_ELEMENT_WORDS; ++i) \
577*c87b03e5Sespie { \
578*c87b03e5Sespie f1 = from1_tmp->bits[i]; \
579*c87b03e5Sespie f2 = from2_tmp->bits[i]; \
580*c87b03e5Sespie t = f1 OP f2; \
581*c87b03e5Sespie changed |= (t != to_tmp->bits[i]); \
582*c87b03e5Sespie to_tmp->bits[i] = t; \
583*c87b03e5Sespie } \
584*c87b03e5Sespie } while (0)
585*c87b03e5Sespie #endif
586*c87b03e5Sespie
587*c87b03e5Sespie to->first = to->current = 0;
588*c87b03e5Sespie
589*c87b03e5Sespie while (from1_ptr != 0 || from2_ptr != 0)
590*c87b03e5Sespie {
591*c87b03e5Sespie /* Figure out whether we need to substitute zero elements for
592*c87b03e5Sespie missing links. */
593*c87b03e5Sespie if (indx1 == indx2)
594*c87b03e5Sespie {
595*c87b03e5Sespie indx = indx1;
596*c87b03e5Sespie from1_tmp = from1_ptr;
597*c87b03e5Sespie from2_tmp = from2_ptr;
598*c87b03e5Sespie from1_ptr = from1_ptr->next;
599*c87b03e5Sespie indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX;
600*c87b03e5Sespie from2_ptr = from2_ptr->next;
601*c87b03e5Sespie indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX;
602*c87b03e5Sespie }
603*c87b03e5Sespie else if (indx1 < indx2)
604*c87b03e5Sespie {
605*c87b03e5Sespie indx = indx1;
606*c87b03e5Sespie from1_tmp = from1_ptr;
607*c87b03e5Sespie from2_tmp = &bitmap_zero_bits;
608*c87b03e5Sespie from1_ptr = from1_ptr->next;
609*c87b03e5Sespie indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX;
610*c87b03e5Sespie }
611*c87b03e5Sespie else
612*c87b03e5Sespie {
613*c87b03e5Sespie indx = indx2;
614*c87b03e5Sespie from1_tmp = &bitmap_zero_bits;
615*c87b03e5Sespie from2_tmp = from2_ptr;
616*c87b03e5Sespie from2_ptr = from2_ptr->next;
617*c87b03e5Sespie indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX;
618*c87b03e5Sespie }
619*c87b03e5Sespie
620*c87b03e5Sespie /* Find the appropriate element from TO. Begin by discarding
621*c87b03e5Sespie elements that we've skipped. */
622*c87b03e5Sespie while (to_ptr && to_ptr->indx < indx)
623*c87b03e5Sespie {
624*c87b03e5Sespie changed = 1;
625*c87b03e5Sespie to_tmp = to_ptr;
626*c87b03e5Sespie to_ptr = to_ptr->next;
627*c87b03e5Sespie bitmap_elem_to_freelist (to, to_tmp);
628*c87b03e5Sespie }
629*c87b03e5Sespie if (to_ptr && to_ptr->indx == indx)
630*c87b03e5Sespie {
631*c87b03e5Sespie to_tmp = to_ptr;
632*c87b03e5Sespie to_ptr = to_ptr->next;
633*c87b03e5Sespie }
634*c87b03e5Sespie else
635*c87b03e5Sespie to_tmp = bitmap_element_allocate (to);
636*c87b03e5Sespie
637*c87b03e5Sespie /* Do the operation, and if any bits are set, link it into the
638*c87b03e5Sespie linked list. */
639*c87b03e5Sespie switch (operation)
640*c87b03e5Sespie {
641*c87b03e5Sespie default:
642*c87b03e5Sespie abort ();
643*c87b03e5Sespie
644*c87b03e5Sespie case BITMAP_AND:
645*c87b03e5Sespie DOIT (&);
646*c87b03e5Sespie break;
647*c87b03e5Sespie
648*c87b03e5Sespie case BITMAP_AND_COMPL:
649*c87b03e5Sespie DOIT (&~);
650*c87b03e5Sespie break;
651*c87b03e5Sespie
652*c87b03e5Sespie case BITMAP_IOR:
653*c87b03e5Sespie DOIT (|);
654*c87b03e5Sespie break;
655*c87b03e5Sespie case BITMAP_IOR_COMPL:
656*c87b03e5Sespie DOIT (|~);
657*c87b03e5Sespie break;
658*c87b03e5Sespie case BITMAP_XOR:
659*c87b03e5Sespie DOIT (^);
660*c87b03e5Sespie break;
661*c87b03e5Sespie }
662*c87b03e5Sespie
663*c87b03e5Sespie if (! bitmap_element_zerop (to_tmp))
664*c87b03e5Sespie {
665*c87b03e5Sespie to_tmp->indx = indx;
666*c87b03e5Sespie bitmap_element_link (to, to_tmp);
667*c87b03e5Sespie }
668*c87b03e5Sespie else
669*c87b03e5Sespie {
670*c87b03e5Sespie bitmap_elem_to_freelist (to, to_tmp);
671*c87b03e5Sespie }
672*c87b03e5Sespie }
673*c87b03e5Sespie
674*c87b03e5Sespie /* If we have elements of TO left over, free the lot. */
675*c87b03e5Sespie if (to_ptr)
676*c87b03e5Sespie {
677*c87b03e5Sespie changed = 1;
678*c87b03e5Sespie for (to_tmp = to_ptr; to_tmp->next ; to_tmp = to_tmp->next)
679*c87b03e5Sespie continue;
680*c87b03e5Sespie if (to->using_obstack)
681*c87b03e5Sespie {
682*c87b03e5Sespie to_tmp->next = bitmap_free;
683*c87b03e5Sespie bitmap_free = to_ptr;
684*c87b03e5Sespie }
685*c87b03e5Sespie else
686*c87b03e5Sespie {
687*c87b03e5Sespie to_tmp->next = bitmap_ggc_free;
688*c87b03e5Sespie bitmap_ggc_free = to_ptr;
689*c87b03e5Sespie }
690*c87b03e5Sespie }
691*c87b03e5Sespie
692*c87b03e5Sespie #undef DOIT
693*c87b03e5Sespie
694*c87b03e5Sespie return changed;
695*c87b03e5Sespie }
696*c87b03e5Sespie
697*c87b03e5Sespie /* Return true if two bitmaps are identical. */
698*c87b03e5Sespie
699*c87b03e5Sespie int
bitmap_equal_p(a,b)700*c87b03e5Sespie bitmap_equal_p (a, b)
701*c87b03e5Sespie bitmap a;
702*c87b03e5Sespie bitmap b;
703*c87b03e5Sespie {
704*c87b03e5Sespie bitmap_head c;
705*c87b03e5Sespie int ret;
706*c87b03e5Sespie
707*c87b03e5Sespie memset (&c, 0, sizeof (c));
708*c87b03e5Sespie ret = ! bitmap_operation (&c, a, b, BITMAP_XOR);
709*c87b03e5Sespie bitmap_clear (&c);
710*c87b03e5Sespie
711*c87b03e5Sespie return ret;
712*c87b03e5Sespie }
713*c87b03e5Sespie
714*c87b03e5Sespie /* Or into bitmap TO bitmap FROM1 and'ed with the complement of
715*c87b03e5Sespie bitmap FROM2. */
716*c87b03e5Sespie
717*c87b03e5Sespie void
bitmap_ior_and_compl(to,from1,from2)718*c87b03e5Sespie bitmap_ior_and_compl (to, from1, from2)
719*c87b03e5Sespie bitmap to;
720*c87b03e5Sespie bitmap from1;
721*c87b03e5Sespie bitmap from2;
722*c87b03e5Sespie {
723*c87b03e5Sespie bitmap_head tmp;
724*c87b03e5Sespie
725*c87b03e5Sespie tmp.first = tmp.current = 0;
726*c87b03e5Sespie tmp.using_obstack = 0;
727*c87b03e5Sespie
728*c87b03e5Sespie bitmap_operation (&tmp, from1, from2, BITMAP_AND_COMPL);
729*c87b03e5Sespie bitmap_operation (to, to, &tmp, BITMAP_IOR);
730*c87b03e5Sespie bitmap_clear (&tmp);
731*c87b03e5Sespie }
732*c87b03e5Sespie
733*c87b03e5Sespie int
bitmap_union_of_diff(dst,a,b,c)734*c87b03e5Sespie bitmap_union_of_diff (dst, a, b, c)
735*c87b03e5Sespie bitmap dst;
736*c87b03e5Sespie bitmap a;
737*c87b03e5Sespie bitmap b;
738*c87b03e5Sespie bitmap c;
739*c87b03e5Sespie {
740*c87b03e5Sespie bitmap_head tmp;
741*c87b03e5Sespie int changed;
742*c87b03e5Sespie
743*c87b03e5Sespie tmp.first = tmp.current = 0;
744*c87b03e5Sespie tmp.using_obstack = 0;
745*c87b03e5Sespie
746*c87b03e5Sespie bitmap_operation (&tmp, b, c, BITMAP_AND_COMPL);
747*c87b03e5Sespie changed = bitmap_operation (dst, &tmp, a, BITMAP_IOR);
748*c87b03e5Sespie bitmap_clear (&tmp);
749*c87b03e5Sespie
750*c87b03e5Sespie return changed;
751*c87b03e5Sespie }
752*c87b03e5Sespie
753*c87b03e5Sespie /* Initialize a bitmap header. */
754*c87b03e5Sespie
755*c87b03e5Sespie bitmap
bitmap_initialize(head,using_obstack)756*c87b03e5Sespie bitmap_initialize (head, using_obstack)
757*c87b03e5Sespie bitmap head;
758*c87b03e5Sespie int using_obstack;
759*c87b03e5Sespie {
760*c87b03e5Sespie if (head == NULL && ! using_obstack)
761*c87b03e5Sespie head = ggc_alloc (sizeof (*head));
762*c87b03e5Sespie
763*c87b03e5Sespie head->first = head->current = 0;
764*c87b03e5Sespie head->using_obstack = using_obstack;
765*c87b03e5Sespie
766*c87b03e5Sespie return head;
767*c87b03e5Sespie }
768*c87b03e5Sespie
769*c87b03e5Sespie /* Debugging function to print out the contents of a bitmap. */
770*c87b03e5Sespie
771*c87b03e5Sespie void
debug_bitmap_file(file,head)772*c87b03e5Sespie debug_bitmap_file (file, head)
773*c87b03e5Sespie FILE *file;
774*c87b03e5Sespie bitmap head;
775*c87b03e5Sespie {
776*c87b03e5Sespie bitmap_element *ptr;
777*c87b03e5Sespie
778*c87b03e5Sespie fprintf (file, "\nfirst = ");
779*c87b03e5Sespie fprintf (file, HOST_PTR_PRINTF, (PTR) head->first);
780*c87b03e5Sespie fprintf (file, " current = ");
781*c87b03e5Sespie fprintf (file, HOST_PTR_PRINTF, (PTR) head->current);
782*c87b03e5Sespie fprintf (file, " indx = %u\n", head->indx);
783*c87b03e5Sespie
784*c87b03e5Sespie for (ptr = head->first; ptr; ptr = ptr->next)
785*c87b03e5Sespie {
786*c87b03e5Sespie unsigned int i, j, col = 26;
787*c87b03e5Sespie
788*c87b03e5Sespie fprintf (file, "\t");
789*c87b03e5Sespie fprintf (file, HOST_PTR_PRINTF, (PTR) ptr);
790*c87b03e5Sespie fprintf (file, " next = ");
791*c87b03e5Sespie fprintf (file, HOST_PTR_PRINTF, (PTR) ptr->next);
792*c87b03e5Sespie fprintf (file, " prev = ");
793*c87b03e5Sespie fprintf (file, HOST_PTR_PRINTF, (PTR) ptr->prev);
794*c87b03e5Sespie fprintf (file, " indx = %u\n\t\tbits = {", ptr->indx);
795*c87b03e5Sespie
796*c87b03e5Sespie for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
797*c87b03e5Sespie for (j = 0; j < BITMAP_WORD_BITS; j++)
798*c87b03e5Sespie if ((ptr->bits[i] >> j) & 1)
799*c87b03e5Sespie {
800*c87b03e5Sespie if (col > 70)
801*c87b03e5Sespie {
802*c87b03e5Sespie fprintf (file, "\n\t\t\t");
803*c87b03e5Sespie col = 24;
804*c87b03e5Sespie }
805*c87b03e5Sespie
806*c87b03e5Sespie fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
807*c87b03e5Sespie + i * BITMAP_WORD_BITS + j));
808*c87b03e5Sespie col += 4;
809*c87b03e5Sespie }
810*c87b03e5Sespie
811*c87b03e5Sespie fprintf (file, " }\n");
812*c87b03e5Sespie }
813*c87b03e5Sespie }
814*c87b03e5Sespie
815*c87b03e5Sespie /* Function to be called from the debugger to print the contents
816*c87b03e5Sespie of a bitmap. */
817*c87b03e5Sespie
818*c87b03e5Sespie void
debug_bitmap(head)819*c87b03e5Sespie debug_bitmap (head)
820*c87b03e5Sespie bitmap head;
821*c87b03e5Sespie {
822*c87b03e5Sespie debug_bitmap_file (stdout, head);
823*c87b03e5Sespie }
824*c87b03e5Sespie
825*c87b03e5Sespie /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
826*c87b03e5Sespie it does not print anything but the bits. */
827*c87b03e5Sespie
828*c87b03e5Sespie void
bitmap_print(file,head,prefix,suffix)829*c87b03e5Sespie bitmap_print (file, head, prefix, suffix)
830*c87b03e5Sespie FILE *file;
831*c87b03e5Sespie bitmap head;
832*c87b03e5Sespie const char *prefix;
833*c87b03e5Sespie const char *suffix;
834*c87b03e5Sespie {
835*c87b03e5Sespie const char *comma = "";
836*c87b03e5Sespie int i;
837*c87b03e5Sespie
838*c87b03e5Sespie fputs (prefix, file);
839*c87b03e5Sespie EXECUTE_IF_SET_IN_BITMAP (head, 0, i,
840*c87b03e5Sespie {
841*c87b03e5Sespie fprintf (file, "%s%d", comma, i);
842*c87b03e5Sespie comma = ", ";
843*c87b03e5Sespie });
844*c87b03e5Sespie fputs (suffix, file);
845*c87b03e5Sespie }
846*c87b03e5Sespie
847*c87b03e5Sespie #include "gt-bitmap.h"
848