1/* Functions to support general ended bitmaps.
2   Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
3   Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING.  If not, write to the Free
19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2002110-1301, USA.  */
21
22#ifndef GCC_BITMAP_H
23#define GCC_BITMAP_H
24
25/* Fundamental storage type for bitmap.  */
26
27typedef unsigned long BITMAP_WORD;
28/* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
29   it is used in preprocessor directives -- hence the 1u.  */
30#define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
31
32/* Number of words to use for each element in the linked list.  */
33
34#ifndef BITMAP_ELEMENT_WORDS
35#define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
36#endif
37
38/* Number of bits in each actual element of a bitmap.  */
39
40#define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
41
42/* Obstack for allocating bitmaps and elements from.  */
43typedef struct bitmap_obstack GTY (())
44{
45  struct bitmap_element_def *elements;
46  struct bitmap_head_def *heads;
47  struct obstack GTY ((skip)) obstack;
48} bitmap_obstack;
49
50/* Bitmap set element.  We use a linked list to hold only the bits that
51   are set.  This allows for use to grow the bitset dynamically without
52   having to realloc and copy a giant bit array.
53
54   The free list is implemented as a list of lists.  There is one
55   outer list connected together by prev fields.  Each element of that
56   outer is an inner list (that may consist only of the outer list
57   element) that are connected by the next fields.  The prev pointer
58   is undefined for interior elements.  This allows
59   bitmap_elt_clear_from to be implemented in unit time rather than
60   linear in the number of elements to be freed.  */
61
62typedef struct bitmap_element_def GTY(())
63{
64  struct bitmap_element_def *next;		/* Next element.  */
65  struct bitmap_element_def *prev;		/* Previous element.  */
66  unsigned int indx;			/* regno/BITMAP_ELEMENT_ALL_BITS.  */
67  BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set.  */
68} bitmap_element;
69
70/* Head of bitmap linked list.  */
71typedef struct bitmap_head_def GTY(()) {
72  bitmap_element *first;	/* First element in linked list.  */
73  bitmap_element *current;	/* Last element looked at.  */
74  unsigned int indx;		/* Index of last element looked at.  */
75  bitmap_obstack *obstack;	/* Obstack to allocate elements from.
76				   If NULL, then use ggc_alloc.  */
77} bitmap_head;
78
79
80typedef struct bitmap_head_def *bitmap;
81
82/* Global data */
83extern bitmap_element bitmap_zero_bits;	/* Zero bitmap element */
84extern bitmap_obstack bitmap_default_obstack;   /* Default bitmap obstack */
85
86/* Clear a bitmap by freeing up the linked list.  */
87extern void bitmap_clear (bitmap);
88
89/* Copy a bitmap to another bitmap.  */
90extern void bitmap_copy (bitmap, bitmap);
91
92/* True if two bitmaps are identical.  */
93extern bool bitmap_equal_p (bitmap, bitmap);
94
95/* True if the bitmaps intersect (their AND is non-empty).  */
96extern bool bitmap_intersect_p (bitmap, bitmap);
97
98/* True if the complement of the second intersects the first (their
99   AND_COMPL is non-empty).  */
100extern bool bitmap_intersect_compl_p (bitmap, bitmap);
101
102/* True if MAP is an empty bitmap.  */
103#define bitmap_empty_p(MAP) (!(MAP)->first)
104
105/* Boolean operations on bitmaps.  The _into variants are two operand
106   versions that modify the first source operand.  The other variants
107   are three operand versions that to not destroy the source bitmaps.
108   The operations supported are &, & ~, |, ^.  */
109extern void bitmap_and (bitmap, bitmap, bitmap);
110extern void bitmap_and_into (bitmap, bitmap);
111extern void bitmap_and_compl (bitmap, bitmap, bitmap);
112extern bool bitmap_and_compl_into (bitmap, bitmap);
113extern bool bitmap_ior (bitmap, bitmap, bitmap);
114extern bool bitmap_ior_into (bitmap, bitmap);
115extern void bitmap_xor (bitmap, bitmap, bitmap);
116extern void bitmap_xor_into (bitmap, bitmap);
117
118/* DST = A | (B & ~C).  Return true if DST changes.  */
119extern bool bitmap_ior_and_compl (bitmap DST, bitmap A, bitmap B, bitmap C);
120/* A |= (B & ~C).  Return true if A changes.  */
121extern bool bitmap_ior_and_compl_into (bitmap DST, bitmap B, bitmap C);
122
123/* Clear a single register in a register set.  */
124extern void bitmap_clear_bit (bitmap, int);
125
126/* Set a single register in a register set.  */
127extern void bitmap_set_bit (bitmap, int);
128
129/* Return true if a register is set in a register set.  */
130extern int bitmap_bit_p (bitmap, int);
131
132/* Debug functions to print a bitmap linked list.  */
133extern void debug_bitmap (bitmap);
134extern void debug_bitmap_file (FILE *, bitmap);
135
136/* Print a bitmap.  */
137extern void bitmap_print (FILE *, bitmap, const char *, const char *);
138
139/* Initialize and release a bitmap obstack.  */
140extern void bitmap_obstack_initialize (bitmap_obstack *);
141extern void bitmap_obstack_release (bitmap_obstack *);
142
143/* Initialize a bitmap header.  OBSTACK indicates the bitmap obstack
144   to allocate from, NULL for GC'd bitmap.  */
145
146static inline void
147bitmap_initialize (bitmap head, bitmap_obstack *obstack)
148{
149  head->first = head->current = NULL;
150  head->obstack = obstack;
151}
152
153/* Allocate and free bitmaps from obstack, malloc and gc'd memory.  */
154extern bitmap bitmap_obstack_alloc (bitmap_obstack *obstack);
155extern bitmap bitmap_gc_alloc (void);
156extern void bitmap_obstack_free (bitmap);
157
158/* A few compatibility/functions macros for compatibility with sbitmaps */
159#define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
160#define bitmap_zero(a) bitmap_clear (a)
161extern unsigned bitmap_first_set_bit (bitmap);
162
163/* Allocate a bitmap from a bit obstack.  */
164#define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK)
165
166/* Allocate a gc'd bitmap.  */
167#define BITMAP_GGC_ALLOC() bitmap_gc_alloc ()
168
169/* Do any cleanup needed on a bitmap when it is no longer used.  */
170#define BITMAP_FREE(BITMAP)			\
171      	((void)(bitmap_obstack_free (BITMAP), (BITMAP) = NULL))
172
173/* Iterator for bitmaps.  */
174
175typedef struct
176{
177  /* Pointer to the current bitmap element.  */
178  bitmap_element *elt1;
179
180  /* Pointer to 2nd bitmap element when two are involved.  */
181  bitmap_element *elt2;
182
183  /* Word within the current element.  */
184  unsigned word_no;
185
186  /* Contents of the actually processed word.  When finding next bit
187     it is shifted right, so that the actual bit is always the least
188     significant bit of ACTUAL.  */
189  BITMAP_WORD bits;
190} bitmap_iterator;
191
192/* Initialize a single bitmap iterator.  START_BIT is the first bit to
193   iterate from.  */
194
195static inline void
196bmp_iter_set_init (bitmap_iterator *bi, bitmap map,
197		   unsigned start_bit, unsigned *bit_no)
198{
199  bi->elt1 = map->first;
200  bi->elt2 = NULL;
201
202  /* Advance elt1 until it is not before the block containing start_bit.  */
203  while (1)
204    {
205      if (!bi->elt1)
206	{
207	  bi->elt1 = &bitmap_zero_bits;
208	  break;
209	}
210
211      if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
212	break;
213      bi->elt1 = bi->elt1->next;
214    }
215
216  /* We might have gone past the start bit, so reinitialize it.  */
217  if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
218    start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
219
220  /* Initialize for what is now start_bit.  */
221  bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
222  bi->bits = bi->elt1->bits[bi->word_no];
223  bi->bits >>= start_bit % BITMAP_WORD_BITS;
224
225  /* If this word is zero, we must make sure we're not pointing at the
226     first bit, otherwise our incrementing to the next word boundary
227     will fail.  It won't matter if this increment moves us into the
228     next word.  */
229  start_bit += !bi->bits;
230
231  *bit_no = start_bit;
232}
233
234/* Initialize an iterator to iterate over the intersection of two
235   bitmaps.  START_BIT is the bit to commence from.  */
236
237static inline void
238bmp_iter_and_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
239		   unsigned start_bit, unsigned *bit_no)
240{
241  bi->elt1 = map1->first;
242  bi->elt2 = map2->first;
243
244  /* Advance elt1 until it is not before the block containing
245     start_bit.  */
246  while (1)
247    {
248      if (!bi->elt1)
249	{
250	  bi->elt2 = NULL;
251	  break;
252	}
253
254      if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
255	break;
256      bi->elt1 = bi->elt1->next;
257    }
258
259  /* Advance elt2 until it is not before elt1.  */
260  while (1)
261    {
262      if (!bi->elt2)
263	{
264	  bi->elt1 = bi->elt2 = &bitmap_zero_bits;
265	  break;
266	}
267
268      if (bi->elt2->indx >= bi->elt1->indx)
269	break;
270      bi->elt2 = bi->elt2->next;
271    }
272
273  /* If we're at the same index, then we have some intersecting bits.  */
274  if (bi->elt1->indx == bi->elt2->indx)
275    {
276      /* We might have advanced beyond the start_bit, so reinitialize
277     	 for that.  */
278      if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
279	start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
280
281      bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
282      bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
283      bi->bits >>= start_bit % BITMAP_WORD_BITS;
284    }
285  else
286    {
287      /* Otherwise we must immediately advance elt1, so initialize for
288	 that.  */
289      bi->word_no = BITMAP_ELEMENT_WORDS - 1;
290      bi->bits = 0;
291    }
292
293  /* If this word is zero, we must make sure we're not pointing at the
294     first bit, otherwise our incrementing to the next word boundary
295     will fail.  It won't matter if this increment moves us into the
296     next word.  */
297  start_bit += !bi->bits;
298
299  *bit_no = start_bit;
300}
301
302/* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2.
303   */
304
305static inline void
306bmp_iter_and_compl_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
307			 unsigned start_bit, unsigned *bit_no)
308{
309  bi->elt1 = map1->first;
310  bi->elt2 = map2->first;
311
312  /* Advance elt1 until it is not before the block containing start_bit.  */
313  while (1)
314    {
315      if (!bi->elt1)
316	{
317	  bi->elt1 = &bitmap_zero_bits;
318	  break;
319	}
320
321      if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
322	break;
323      bi->elt1 = bi->elt1->next;
324    }
325
326  /* Advance elt2 until it is not before elt1.  */
327  while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
328    bi->elt2 = bi->elt2->next;
329
330  /* We might have advanced beyond the start_bit, so reinitialize for
331     that.  */
332  if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
333    start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
334
335  bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
336  bi->bits = bi->elt1->bits[bi->word_no];
337  if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
338    bi->bits &= ~bi->elt2->bits[bi->word_no];
339  bi->bits >>= start_bit % BITMAP_WORD_BITS;
340
341  /* If this word is zero, we must make sure we're not pointing at the
342     first bit, otherwise our incrementing to the next word boundary
343     will fail.  It won't matter if this increment moves us into the
344     next word.  */
345  start_bit += !bi->bits;
346
347  *bit_no = start_bit;
348}
349
350/* Advance to the next bit in BI.  We don't advance to the next
351   nonzero bit yet.  */
352
353static inline void
354bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
355{
356  bi->bits >>= 1;
357  *bit_no += 1;
358}
359
360/* Advance to the next nonzero bit of a single bitmap, we will have
361   already advanced past the just iterated bit.  Return true if there
362   is a bit to iterate.  */
363
364static inline bool
365bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
366{
367  /* If our current word is nonzero, it contains the bit we want.  */
368  if (bi->bits)
369    {
370    next_bit:
371      while (!(bi->bits & 1))
372	{
373	  bi->bits >>= 1;
374	  *bit_no += 1;
375	}
376      return true;
377    }
378
379  /* Round up to the word boundary.  We might have just iterated past
380     the end of the last word, hence the -1.  It is not possible for
381     bit_no to point at the beginning of the now last word.  */
382  *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
383	     / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
384  bi->word_no++;
385
386  while (1)
387    {
388      /* Find the next nonzero word in this elt.  */
389      while (bi->word_no != BITMAP_ELEMENT_WORDS)
390	{
391	  bi->bits = bi->elt1->bits[bi->word_no];
392	  if (bi->bits)
393	    goto next_bit;
394	  *bit_no += BITMAP_WORD_BITS;
395	  bi->word_no++;
396	}
397
398      /* Advance to the next element.  */
399      bi->elt1 = bi->elt1->next;
400      if (!bi->elt1)
401	return false;
402      *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
403      bi->word_no = 0;
404    }
405}
406
407/* Advance to the next nonzero bit of an intersecting pair of
408   bitmaps.  We will have already advanced past the just iterated bit.
409   Return true if there is a bit to iterate.  */
410
411static inline bool
412bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
413{
414  /* If our current word is nonzero, it contains the bit we want.  */
415  if (bi->bits)
416    {
417    next_bit:
418      while (!(bi->bits & 1))
419	{
420	  bi->bits >>= 1;
421	  *bit_no += 1;
422	}
423      return true;
424    }
425
426  /* Round up to the word boundary.  We might have just iterated past
427     the end of the last word, hence the -1.  It is not possible for
428     bit_no to point at the beginning of the now last word.  */
429  *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
430	     / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
431  bi->word_no++;
432
433  while (1)
434    {
435      /* Find the next nonzero word in this elt.  */
436      while (bi->word_no != BITMAP_ELEMENT_WORDS)
437	{
438	  bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
439	  if (bi->bits)
440	    goto next_bit;
441	  *bit_no += BITMAP_WORD_BITS;
442	  bi->word_no++;
443	}
444
445      /* Advance to the next identical element.  */
446      do
447	{
448	  /* Advance elt1 while it is less than elt2.  We always want
449	     to advance one elt.  */
450	  do
451	    {
452	      bi->elt1 = bi->elt1->next;
453	      if (!bi->elt1)
454		return false;
455	    }
456	  while (bi->elt1->indx < bi->elt2->indx);
457
458	  /* Advance elt2 to be no less than elt1.  This might not
459	     advance.  */
460	  while (bi->elt2->indx < bi->elt1->indx)
461	    {
462	      bi->elt2 = bi->elt2->next;
463	      if (!bi->elt2)
464		return false;
465	    }
466	}
467      while (bi->elt1->indx != bi->elt2->indx);
468
469      *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
470      bi->word_no = 0;
471    }
472}
473
474/* Advance to the next nonzero bit in the intersection of
475   complemented bitmaps.  We will have already advanced past the just
476   iterated bit.  */
477
478static inline bool
479bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
480{
481  /* If our current word is nonzero, it contains the bit we want.  */
482  if (bi->bits)
483    {
484    next_bit:
485      while (!(bi->bits & 1))
486	{
487	  bi->bits >>= 1;
488	  *bit_no += 1;
489	}
490      return true;
491    }
492
493  /* Round up to the word boundary.  We might have just iterated past
494     the end of the last word, hence the -1.  It is not possible for
495     bit_no to point at the beginning of the now last word.  */
496  *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
497	     / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
498  bi->word_no++;
499
500  while (1)
501    {
502      /* Find the next nonzero word in this elt.  */
503      while (bi->word_no != BITMAP_ELEMENT_WORDS)
504	{
505	  bi->bits = bi->elt1->bits[bi->word_no];
506	  if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
507	    bi->bits &= ~bi->elt2->bits[bi->word_no];
508	  if (bi->bits)
509	    goto next_bit;
510	  *bit_no += BITMAP_WORD_BITS;
511	  bi->word_no++;
512	}
513
514      /* Advance to the next element of elt1.  */
515      bi->elt1 = bi->elt1->next;
516      if (!bi->elt1)
517	return false;
518
519      /* Advance elt2 until it is no less than elt1.  */
520      while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
521	bi->elt2 = bi->elt2->next;
522
523      *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
524      bi->word_no = 0;
525    }
526}
527
528/* Loop over all bits set in BITMAP, starting with MIN and setting
529   BITNUM to the bit number.  ITER is a bitmap iterator.  BITNUM
530   should be treated as a read-only variable as it contains loop
531   state.  */
532
533#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)		\
534  for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM));		\
535       bmp_iter_set (&(ITER), &(BITNUM));				\
536       bmp_iter_next (&(ITER), &(BITNUM)))
537
538/* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
539   and setting BITNUM to the bit number.  ITER is a bitmap iterator.
540   BITNUM should be treated as a read-only variable as it contains
541   loop state.  */
542
543#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER)	\
544  for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), 	\
545			  &(BITNUM));					\
546       bmp_iter_and (&(ITER), &(BITNUM));				\
547       bmp_iter_next (&(ITER), &(BITNUM)))
548
549/* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
550   and setting BITNUM to the bit number.  ITER is a bitmap iterator.
551   BITNUM should be treated as a read-only variable as it contains
552   loop state.  */
553
554#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
555  for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),	\
556				&(BITNUM)); 				\
557       bmp_iter_and_compl (&(ITER), &(BITNUM));				\
558       bmp_iter_next (&(ITER), &(BITNUM)))
559
560#endif /* GCC_BITMAP_H */
561