1*38fd1498Szrj /* Functions to support general ended bitmaps.
2*38fd1498Szrj Copyright (C) 1997-2018 Free Software Foundation, Inc.
3*38fd1498Szrj
4*38fd1498Szrj This file is part of GCC.
5*38fd1498Szrj
6*38fd1498Szrj GCC is free software; you can redistribute it and/or modify it under
7*38fd1498Szrj the terms of the GNU General Public License as published by the Free
8*38fd1498Szrj Software Foundation; either version 3, or (at your option) any later
9*38fd1498Szrj version.
10*38fd1498Szrj
11*38fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12*38fd1498Szrj WARRANTY; without even the implied warranty of MERCHANTABILITY or
13*38fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14*38fd1498Szrj for more details.
15*38fd1498Szrj
16*38fd1498Szrj You should have received a copy of the GNU General Public License
17*38fd1498Szrj along with GCC; see the file COPYING3. If not see
18*38fd1498Szrj <http://www.gnu.org/licenses/>. */
19*38fd1498Szrj
20*38fd1498Szrj #ifndef GCC_BITMAP_H
21*38fd1498Szrj #define GCC_BITMAP_H
22*38fd1498Szrj
23*38fd1498Szrj /* Implementation of sparse integer sets as a linked list.
24*38fd1498Szrj
25*38fd1498Szrj This sparse set representation is suitable for sparse sets with an
26*38fd1498Szrj unknown (a priori) universe. The set is represented as a double-linked
27*38fd1498Szrj list of container nodes (struct bitmap_element). Each node consists
28*38fd1498Szrj of an index for the first member that could be held in the container,
29*38fd1498Szrj a small array of integers that represent the members in the container,
30*38fd1498Szrj and pointers to the next and previous element in the linked list. The
31*38fd1498Szrj elements in the list are sorted in ascending order, i.e. the head of
32*38fd1498Szrj the list holds the element with the smallest member of the set.
33*38fd1498Szrj
34*38fd1498Szrj For a given member I in the set:
35*38fd1498Szrj - the element for I will have index is I / (bits per element)
36*38fd1498Szrj - the position for I within element is I % (bits per element)
37*38fd1498Szrj
38*38fd1498Szrj This representation is very space-efficient for large sparse sets, and
39*38fd1498Szrj the size of the set can be changed dynamically without much overhead.
40*38fd1498Szrj An important parameter is the number of bits per element. In this
41*38fd1498Szrj implementation, there are 128 bits per element. This results in a
42*38fd1498Szrj high storage overhead *per element*, but a small overall overhead if
43*38fd1498Szrj the set is very sparse.
44*38fd1498Szrj
45*38fd1498Szrj The downside is that many operations are relatively slow because the
46*38fd1498Szrj linked list has to be traversed to test membership (i.e. member_p/
47*38fd1498Szrj add_member/remove_member). To improve the performance of this set
48*38fd1498Szrj representation, the last accessed element and its index are cached.
49*38fd1498Szrj For membership tests on members close to recently accessed members,
50*38fd1498Szrj the cached last element improves membership test to a constant-time
51*38fd1498Szrj operation.
52*38fd1498Szrj
53*38fd1498Szrj The following operations can always be performed in O(1) time:
54*38fd1498Szrj
55*38fd1498Szrj * clear : bitmap_clear
56*38fd1498Szrj * choose_one : (not implemented, but could be
57*38fd1498Szrj implemented in constant time)
58*38fd1498Szrj
59*38fd1498Szrj The following operations can be performed in O(E) time worst-case (with
60*38fd1498Szrj E the number of elements in the linked list), but in O(1) time with a
61*38fd1498Szrj suitable access patterns:
62*38fd1498Szrj
63*38fd1498Szrj * member_p : bitmap_bit_p
64*38fd1498Szrj * add_member : bitmap_set_bit
65*38fd1498Szrj * remove_member : bitmap_clear_bit
66*38fd1498Szrj
67*38fd1498Szrj The following operations can be performed in O(E) time:
68*38fd1498Szrj
69*38fd1498Szrj * cardinality : bitmap_count_bits
70*38fd1498Szrj * set_size : bitmap_last_set_bit (but this could
71*38fd1498Szrj in constant time with a pointer to
72*38fd1498Szrj the last element in the chain)
73*38fd1498Szrj
74*38fd1498Szrj Additionally, the linked-list sparse set representation supports
75*38fd1498Szrj enumeration of the members in O(E) time:
76*38fd1498Szrj
77*38fd1498Szrj * forall : EXECUTE_IF_SET_IN_BITMAP
78*38fd1498Szrj * set_copy : bitmap_copy
79*38fd1498Szrj * set_intersection : bitmap_intersect_p /
80*38fd1498Szrj bitmap_and / bitmap_and_into /
81*38fd1498Szrj EXECUTE_IF_AND_IN_BITMAP
82*38fd1498Szrj * set_union : bitmap_ior / bitmap_ior_into
83*38fd1498Szrj * set_difference : bitmap_intersect_compl_p /
84*38fd1498Szrj bitmap_and_comp / bitmap_and_comp_into /
85*38fd1498Szrj EXECUTE_IF_AND_COMPL_IN_BITMAP
86*38fd1498Szrj * set_disjuction : bitmap_xor_comp / bitmap_xor_comp_into
87*38fd1498Szrj * set_compare : bitmap_equal_p
88*38fd1498Szrj
89*38fd1498Szrj Some operations on 3 sets that occur frequently in data flow problems
90*38fd1498Szrj are also implemented:
91*38fd1498Szrj
92*38fd1498Szrj * A | (B & C) : bitmap_ior_and_into
93*38fd1498Szrj * A | (B & ~C) : bitmap_ior_and_compl /
94*38fd1498Szrj bitmap_ior_and_compl_into
95*38fd1498Szrj
96*38fd1498Szrj The storage requirements for linked-list sparse sets are O(E), with E->N
97*38fd1498Szrj in the worst case (a sparse set with large distances between the values
98*38fd1498Szrj of the set members).
99*38fd1498Szrj
100*38fd1498Szrj The linked-list set representation works well for problems involving very
101*38fd1498Szrj sparse sets. The canonical example in GCC is, of course, the "set of
102*38fd1498Szrj sets" for some CFG-based data flow problems (liveness analysis, dominance
103*38fd1498Szrj frontiers, etc.).
104*38fd1498Szrj
105*38fd1498Szrj This representation also works well for data flow problems where the size
106*38fd1498Szrj of the set may grow dynamically, but care must be taken that the member_p,
107*38fd1498Szrj add_member, and remove_member operations occur with a suitable access
108*38fd1498Szrj pattern.
109*38fd1498Szrj
110*38fd1498Szrj For random-access sets with a known, relatively small universe size, the
111*38fd1498Szrj SparseSet or simple bitmap representations may be more efficient than a
112*38fd1498Szrj linked-list set. For random-access sets of unknown universe, a hash table
113*38fd1498Szrj or a balanced binary tree representation is likely to be a more suitable
114*38fd1498Szrj choice.
115*38fd1498Szrj
116*38fd1498Szrj Traversing linked lists is usually cache-unfriendly, even with the last
117*38fd1498Szrj accessed element cached.
118*38fd1498Szrj
119*38fd1498Szrj Cache performance can be improved by keeping the elements in the set
120*38fd1498Szrj grouped together in memory, using a dedicated obstack for a set (or group
121*38fd1498Szrj of related sets). Elements allocated on obstacks are released to a
122*38fd1498Szrj free-list and taken off the free list. If multiple sets are allocated on
123*38fd1498Szrj the same obstack, elements freed from one set may be re-used for one of
124*38fd1498Szrj the other sets. This usually helps avoid cache misses.
125*38fd1498Szrj
126*38fd1498Szrj A single free-list is used for all sets allocated in GGC space. This is
127*38fd1498Szrj bad for persistent sets, so persistent sets should be allocated on an
128*38fd1498Szrj obstack whenever possible. */
129*38fd1498Szrj
130*38fd1498Szrj #include "obstack.h"
131*38fd1498Szrj
132*38fd1498Szrj /* Bitmap memory usage. */
133*38fd1498Szrj struct bitmap_usage: public mem_usage
134*38fd1498Szrj {
135*38fd1498Szrj /* Default contructor. */
bitmap_usagebitmap_usage136*38fd1498Szrj bitmap_usage (): m_nsearches (0), m_search_iter (0) {}
137*38fd1498Szrj /* Constructor. */
bitmap_usagebitmap_usage138*38fd1498Szrj bitmap_usage (size_t allocated, size_t times, size_t peak,
139*38fd1498Szrj uint64_t nsearches, uint64_t search_iter)
140*38fd1498Szrj : mem_usage (allocated, times, peak),
141*38fd1498Szrj m_nsearches (nsearches), m_search_iter (search_iter) {}
142*38fd1498Szrj
143*38fd1498Szrj /* Sum the usage with SECOND usage. */
144*38fd1498Szrj bitmap_usage
145*38fd1498Szrj operator+ (const bitmap_usage &second)
146*38fd1498Szrj {
147*38fd1498Szrj return bitmap_usage (m_allocated + second.m_allocated,
148*38fd1498Szrj m_times + second.m_times,
149*38fd1498Szrj m_peak + second.m_peak,
150*38fd1498Szrj m_nsearches + second.m_nsearches,
151*38fd1498Szrj m_search_iter + second.m_search_iter);
152*38fd1498Szrj }
153*38fd1498Szrj
154*38fd1498Szrj /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
155*38fd1498Szrj inline void
dumpbitmap_usage156*38fd1498Szrj dump (mem_location *loc, mem_usage &total) const
157*38fd1498Szrj {
158*38fd1498Szrj char *location_string = loc->to_string ();
159*38fd1498Szrj
160*38fd1498Szrj fprintf (stderr, "%-48s %10" PRIu64 ":%5.1f%%"
161*38fd1498Szrj "%10" PRIu64 "%10" PRIu64 ":%5.1f%%"
162*38fd1498Szrj "%12" PRIu64 "%12" PRIu64 "%10s\n",
163*38fd1498Szrj location_string, (uint64_t)m_allocated,
164*38fd1498Szrj get_percent (m_allocated, total.m_allocated),
165*38fd1498Szrj (uint64_t)m_peak, (uint64_t)m_times,
166*38fd1498Szrj get_percent (m_times, total.m_times),
167*38fd1498Szrj m_nsearches, m_search_iter,
168*38fd1498Szrj loc->m_ggc ? "ggc" : "heap");
169*38fd1498Szrj
170*38fd1498Szrj free (location_string);
171*38fd1498Szrj }
172*38fd1498Szrj
173*38fd1498Szrj /* Dump header with NAME. */
174*38fd1498Szrj static inline void
dump_headerbitmap_usage175*38fd1498Szrj dump_header (const char *name)
176*38fd1498Szrj {
177*38fd1498Szrj fprintf (stderr, "%-48s %11s%16s%17s%12s%12s%10s\n", name, "Leak", "Peak",
178*38fd1498Szrj "Times", "N searches", "Search iter", "Type");
179*38fd1498Szrj print_dash_line ();
180*38fd1498Szrj }
181*38fd1498Szrj
182*38fd1498Szrj /* Number search operations. */
183*38fd1498Szrj uint64_t m_nsearches;
184*38fd1498Szrj /* Number of search iterations. */
185*38fd1498Szrj uint64_t m_search_iter;
186*38fd1498Szrj };
187*38fd1498Szrj
188*38fd1498Szrj /* Bitmap memory description. */
189*38fd1498Szrj extern mem_alloc_description<bitmap_usage> bitmap_mem_desc;
190*38fd1498Szrj
191*38fd1498Szrj /* Fundamental storage type for bitmap. */
192*38fd1498Szrj
193*38fd1498Szrj typedef unsigned long BITMAP_WORD;
194*38fd1498Szrj /* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
195*38fd1498Szrj it is used in preprocessor directives -- hence the 1u. */
196*38fd1498Szrj #define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
197*38fd1498Szrj
198*38fd1498Szrj /* Number of words to use for each element in the linked list. */
199*38fd1498Szrj
200*38fd1498Szrj #ifndef BITMAP_ELEMENT_WORDS
201*38fd1498Szrj #define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
202*38fd1498Szrj #endif
203*38fd1498Szrj
204*38fd1498Szrj /* Number of bits in each actual element of a bitmap. */
205*38fd1498Szrj
206*38fd1498Szrj #define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
207*38fd1498Szrj
208*38fd1498Szrj /* Obstack for allocating bitmaps and elements from. */
209*38fd1498Szrj struct GTY (()) bitmap_obstack {
210*38fd1498Szrj struct bitmap_element *elements;
211*38fd1498Szrj struct bitmap_head *heads;
212*38fd1498Szrj struct obstack GTY ((skip)) obstack;
213*38fd1498Szrj };
214*38fd1498Szrj
215*38fd1498Szrj /* Bitmap set element. We use a linked list to hold only the bits that
216*38fd1498Szrj are set. This allows for use to grow the bitset dynamically without
217*38fd1498Szrj having to realloc and copy a giant bit array.
218*38fd1498Szrj
219*38fd1498Szrj The free list is implemented as a list of lists. There is one
220*38fd1498Szrj outer list connected together by prev fields. Each element of that
221*38fd1498Szrj outer is an inner list (that may consist only of the outer list
222*38fd1498Szrj element) that are connected by the next fields. The prev pointer
223*38fd1498Szrj is undefined for interior elements. This allows
224*38fd1498Szrj bitmap_elt_clear_from to be implemented in unit time rather than
225*38fd1498Szrj linear in the number of elements to be freed. */
226*38fd1498Szrj
227*38fd1498Szrj struct GTY((chain_next ("%h.next"), chain_prev ("%h.prev"))) bitmap_element {
228*38fd1498Szrj struct bitmap_element *next; /* Next element. */
229*38fd1498Szrj struct bitmap_element *prev; /* Previous element. */
230*38fd1498Szrj unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */
231*38fd1498Szrj BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */
232*38fd1498Szrj };
233*38fd1498Szrj
234*38fd1498Szrj /* Head of bitmap linked list. The 'current' member points to something
235*38fd1498Szrj already pointed to by the chain started by first, so GTY((skip)) it. */
236*38fd1498Szrj
237*38fd1498Szrj struct GTY(()) bitmap_head {
238*38fd1498Szrj unsigned int indx; /* Index of last element looked at. */
239*38fd1498Szrj unsigned int descriptor_id; /* Unique identifier for the allocation
240*38fd1498Szrj site of this bitmap, for detailed
241*38fd1498Szrj statistics gathering. */
242*38fd1498Szrj bitmap_element *first; /* First element in linked list. */
243*38fd1498Szrj bitmap_element * GTY((skip(""))) current; /* Last element looked at. */
244*38fd1498Szrj bitmap_obstack *obstack; /* Obstack to allocate elements from.
245*38fd1498Szrj If NULL, then use GGC allocation. */
246*38fd1498Szrj };
247*38fd1498Szrj
248*38fd1498Szrj /* Global data */
249*38fd1498Szrj extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
250*38fd1498Szrj extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */
251*38fd1498Szrj
252*38fd1498Szrj /* Clear a bitmap by freeing up the linked list. */
253*38fd1498Szrj extern void bitmap_clear (bitmap);
254*38fd1498Szrj
255*38fd1498Szrj /* Copy a bitmap to another bitmap. */
256*38fd1498Szrj extern void bitmap_copy (bitmap, const_bitmap);
257*38fd1498Szrj
258*38fd1498Szrj /* Move a bitmap to another bitmap. */
259*38fd1498Szrj extern void bitmap_move (bitmap, bitmap);
260*38fd1498Szrj
261*38fd1498Szrj /* True if two bitmaps are identical. */
262*38fd1498Szrj extern bool bitmap_equal_p (const_bitmap, const_bitmap);
263*38fd1498Szrj
264*38fd1498Szrj /* True if the bitmaps intersect (their AND is non-empty). */
265*38fd1498Szrj extern bool bitmap_intersect_p (const_bitmap, const_bitmap);
266*38fd1498Szrj
267*38fd1498Szrj /* True if the complement of the second intersects the first (their
268*38fd1498Szrj AND_COMPL is non-empty). */
269*38fd1498Szrj extern bool bitmap_intersect_compl_p (const_bitmap, const_bitmap);
270*38fd1498Szrj
271*38fd1498Szrj /* True if MAP is an empty bitmap. */
bitmap_empty_p(const_bitmap map)272*38fd1498Szrj inline bool bitmap_empty_p (const_bitmap map)
273*38fd1498Szrj {
274*38fd1498Szrj return !map->first;
275*38fd1498Szrj }
276*38fd1498Szrj
277*38fd1498Szrj /* True if the bitmap has only a single bit set. */
278*38fd1498Szrj extern bool bitmap_single_bit_set_p (const_bitmap);
279*38fd1498Szrj
280*38fd1498Szrj /* Count the number of bits set in the bitmap. */
281*38fd1498Szrj extern unsigned long bitmap_count_bits (const_bitmap);
282*38fd1498Szrj
283*38fd1498Szrj /* Count the number of unique bits set across the two bitmaps. */
284*38fd1498Szrj extern unsigned long bitmap_count_unique_bits (const_bitmap, const_bitmap);
285*38fd1498Szrj
286*38fd1498Szrj /* Boolean operations on bitmaps. The _into variants are two operand
287*38fd1498Szrj versions that modify the first source operand. The other variants
288*38fd1498Szrj are three operand versions that to not destroy the source bitmaps.
289*38fd1498Szrj The operations supported are &, & ~, |, ^. */
290*38fd1498Szrj extern void bitmap_and (bitmap, const_bitmap, const_bitmap);
291*38fd1498Szrj extern bool bitmap_and_into (bitmap, const_bitmap);
292*38fd1498Szrj extern bool bitmap_and_compl (bitmap, const_bitmap, const_bitmap);
293*38fd1498Szrj extern bool bitmap_and_compl_into (bitmap, const_bitmap);
294*38fd1498Szrj #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
295*38fd1498Szrj extern void bitmap_compl_and_into (bitmap, const_bitmap);
296*38fd1498Szrj extern void bitmap_clear_range (bitmap, unsigned int, unsigned int);
297*38fd1498Szrj extern void bitmap_set_range (bitmap, unsigned int, unsigned int);
298*38fd1498Szrj extern bool bitmap_ior (bitmap, const_bitmap, const_bitmap);
299*38fd1498Szrj extern bool bitmap_ior_into (bitmap, const_bitmap);
300*38fd1498Szrj extern void bitmap_xor (bitmap, const_bitmap, const_bitmap);
301*38fd1498Szrj extern void bitmap_xor_into (bitmap, const_bitmap);
302*38fd1498Szrj
303*38fd1498Szrj /* DST = A | (B & C). Return true if DST changes. */
304*38fd1498Szrj extern bool bitmap_ior_and_into (bitmap DST, const_bitmap B, const_bitmap C);
305*38fd1498Szrj /* DST = A | (B & ~C). Return true if DST changes. */
306*38fd1498Szrj extern bool bitmap_ior_and_compl (bitmap DST, const_bitmap A,
307*38fd1498Szrj const_bitmap B, const_bitmap C);
308*38fd1498Szrj /* A |= (B & ~C). Return true if A changes. */
309*38fd1498Szrj extern bool bitmap_ior_and_compl_into (bitmap A,
310*38fd1498Szrj const_bitmap B, const_bitmap C);
311*38fd1498Szrj
312*38fd1498Szrj /* Clear a single bit in a bitmap. Return true if the bit changed. */
313*38fd1498Szrj extern bool bitmap_clear_bit (bitmap, int);
314*38fd1498Szrj
315*38fd1498Szrj /* Set a single bit in a bitmap. Return true if the bit changed. */
316*38fd1498Szrj extern bool bitmap_set_bit (bitmap, int);
317*38fd1498Szrj
318*38fd1498Szrj /* Return true if a register is set in a register set. */
319*38fd1498Szrj extern int bitmap_bit_p (bitmap, int);
320*38fd1498Szrj
321*38fd1498Szrj /* Debug functions to print a bitmap linked list. */
322*38fd1498Szrj extern void debug_bitmap (const_bitmap);
323*38fd1498Szrj extern void debug_bitmap_file (FILE *, const_bitmap);
324*38fd1498Szrj
325*38fd1498Szrj /* Print a bitmap. */
326*38fd1498Szrj extern void bitmap_print (FILE *, const_bitmap, const char *, const char *);
327*38fd1498Szrj
328*38fd1498Szrj /* Initialize and release a bitmap obstack. */
329*38fd1498Szrj extern void bitmap_obstack_initialize (bitmap_obstack *);
330*38fd1498Szrj extern void bitmap_obstack_release (bitmap_obstack *);
331*38fd1498Szrj extern void bitmap_register (bitmap MEM_STAT_DECL);
332*38fd1498Szrj extern void dump_bitmap_statistics (void);
333*38fd1498Szrj
334*38fd1498Szrj /* Initialize a bitmap header. OBSTACK indicates the bitmap obstack
335*38fd1498Szrj to allocate from, NULL for GC'd bitmap. */
336*38fd1498Szrj
337*38fd1498Szrj static inline void
bitmap_initialize(bitmap head,bitmap_obstack * obstack CXX_MEM_STAT_INFO)338*38fd1498Szrj bitmap_initialize (bitmap head, bitmap_obstack *obstack CXX_MEM_STAT_INFO)
339*38fd1498Szrj {
340*38fd1498Szrj head->first = head->current = NULL;
341*38fd1498Szrj head->obstack = obstack;
342*38fd1498Szrj if (GATHER_STATISTICS)
343*38fd1498Szrj bitmap_register (head PASS_MEM_STAT);
344*38fd1498Szrj }
345*38fd1498Szrj
346*38fd1498Szrj /* Allocate and free bitmaps from obstack, malloc and gc'd memory. */
347*38fd1498Szrj extern bitmap bitmap_alloc (bitmap_obstack *obstack CXX_MEM_STAT_INFO);
348*38fd1498Szrj #define BITMAP_ALLOC bitmap_alloc
349*38fd1498Szrj extern bitmap bitmap_gc_alloc (ALONE_CXX_MEM_STAT_INFO);
350*38fd1498Szrj #define BITMAP_GGC_ALLOC bitmap_gc_alloc
351*38fd1498Szrj extern void bitmap_obstack_free (bitmap);
352*38fd1498Szrj
353*38fd1498Szrj /* A few compatibility/functions macros for compatibility with sbitmaps */
dump_bitmap(FILE * file,const_bitmap map)354*38fd1498Szrj inline void dump_bitmap (FILE *file, const_bitmap map)
355*38fd1498Szrj {
356*38fd1498Szrj bitmap_print (file, map, "", "\n");
357*38fd1498Szrj }
358*38fd1498Szrj extern void debug (const bitmap_head &ref);
359*38fd1498Szrj extern void debug (const bitmap_head *ptr);
360*38fd1498Szrj
361*38fd1498Szrj extern unsigned bitmap_first_set_bit (const_bitmap);
362*38fd1498Szrj extern unsigned bitmap_last_set_bit (const_bitmap);
363*38fd1498Szrj
364*38fd1498Szrj /* Compute bitmap hash (for purposes of hashing etc.) */
365*38fd1498Szrj extern hashval_t bitmap_hash (const_bitmap);
366*38fd1498Szrj
367*38fd1498Szrj /* Do any cleanup needed on a bitmap when it is no longer used. */
368*38fd1498Szrj #define BITMAP_FREE(BITMAP) \
369*38fd1498Szrj ((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL))
370*38fd1498Szrj
371*38fd1498Szrj /* Iterator for bitmaps. */
372*38fd1498Szrj
373*38fd1498Szrj struct bitmap_iterator
374*38fd1498Szrj {
375*38fd1498Szrj /* Pointer to the current bitmap element. */
376*38fd1498Szrj bitmap_element *elt1;
377*38fd1498Szrj
378*38fd1498Szrj /* Pointer to 2nd bitmap element when two are involved. */
379*38fd1498Szrj bitmap_element *elt2;
380*38fd1498Szrj
381*38fd1498Szrj /* Word within the current element. */
382*38fd1498Szrj unsigned word_no;
383*38fd1498Szrj
384*38fd1498Szrj /* Contents of the actually processed word. When finding next bit
385*38fd1498Szrj it is shifted right, so that the actual bit is always the least
386*38fd1498Szrj significant bit of ACTUAL. */
387*38fd1498Szrj BITMAP_WORD bits;
388*38fd1498Szrj };
389*38fd1498Szrj
390*38fd1498Szrj /* Initialize a single bitmap iterator. START_BIT is the first bit to
391*38fd1498Szrj iterate from. */
392*38fd1498Szrj
393*38fd1498Szrj static inline void
bmp_iter_set_init(bitmap_iterator * bi,const_bitmap map,unsigned start_bit,unsigned * bit_no)394*38fd1498Szrj bmp_iter_set_init (bitmap_iterator *bi, const_bitmap map,
395*38fd1498Szrj unsigned start_bit, unsigned *bit_no)
396*38fd1498Szrj {
397*38fd1498Szrj bi->elt1 = map->first;
398*38fd1498Szrj bi->elt2 = NULL;
399*38fd1498Szrj
400*38fd1498Szrj /* Advance elt1 until it is not before the block containing start_bit. */
401*38fd1498Szrj while (1)
402*38fd1498Szrj {
403*38fd1498Szrj if (!bi->elt1)
404*38fd1498Szrj {
405*38fd1498Szrj bi->elt1 = &bitmap_zero_bits;
406*38fd1498Szrj break;
407*38fd1498Szrj }
408*38fd1498Szrj
409*38fd1498Szrj if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
410*38fd1498Szrj break;
411*38fd1498Szrj bi->elt1 = bi->elt1->next;
412*38fd1498Szrj }
413*38fd1498Szrj
414*38fd1498Szrj /* We might have gone past the start bit, so reinitialize it. */
415*38fd1498Szrj if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
416*38fd1498Szrj start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
417*38fd1498Szrj
418*38fd1498Szrj /* Initialize for what is now start_bit. */
419*38fd1498Szrj bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
420*38fd1498Szrj bi->bits = bi->elt1->bits[bi->word_no];
421*38fd1498Szrj bi->bits >>= start_bit % BITMAP_WORD_BITS;
422*38fd1498Szrj
423*38fd1498Szrj /* If this word is zero, we must make sure we're not pointing at the
424*38fd1498Szrj first bit, otherwise our incrementing to the next word boundary
425*38fd1498Szrj will fail. It won't matter if this increment moves us into the
426*38fd1498Szrj next word. */
427*38fd1498Szrj start_bit += !bi->bits;
428*38fd1498Szrj
429*38fd1498Szrj *bit_no = start_bit;
430*38fd1498Szrj }
431*38fd1498Szrj
432*38fd1498Szrj /* Initialize an iterator to iterate over the intersection of two
433*38fd1498Szrj bitmaps. START_BIT is the bit to commence from. */
434*38fd1498Szrj
435*38fd1498Szrj static inline void
bmp_iter_and_init(bitmap_iterator * bi,const_bitmap map1,const_bitmap map2,unsigned start_bit,unsigned * bit_no)436*38fd1498Szrj bmp_iter_and_init (bitmap_iterator *bi, const_bitmap map1, const_bitmap map2,
437*38fd1498Szrj unsigned start_bit, unsigned *bit_no)
438*38fd1498Szrj {
439*38fd1498Szrj bi->elt1 = map1->first;
440*38fd1498Szrj bi->elt2 = map2->first;
441*38fd1498Szrj
442*38fd1498Szrj /* Advance elt1 until it is not before the block containing
443*38fd1498Szrj start_bit. */
444*38fd1498Szrj while (1)
445*38fd1498Szrj {
446*38fd1498Szrj if (!bi->elt1)
447*38fd1498Szrj {
448*38fd1498Szrj bi->elt2 = NULL;
449*38fd1498Szrj break;
450*38fd1498Szrj }
451*38fd1498Szrj
452*38fd1498Szrj if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
453*38fd1498Szrj break;
454*38fd1498Szrj bi->elt1 = bi->elt1->next;
455*38fd1498Szrj }
456*38fd1498Szrj
457*38fd1498Szrj /* Advance elt2 until it is not before elt1. */
458*38fd1498Szrj while (1)
459*38fd1498Szrj {
460*38fd1498Szrj if (!bi->elt2)
461*38fd1498Szrj {
462*38fd1498Szrj bi->elt1 = bi->elt2 = &bitmap_zero_bits;
463*38fd1498Szrj break;
464*38fd1498Szrj }
465*38fd1498Szrj
466*38fd1498Szrj if (bi->elt2->indx >= bi->elt1->indx)
467*38fd1498Szrj break;
468*38fd1498Szrj bi->elt2 = bi->elt2->next;
469*38fd1498Szrj }
470*38fd1498Szrj
471*38fd1498Szrj /* If we're at the same index, then we have some intersecting bits. */
472*38fd1498Szrj if (bi->elt1->indx == bi->elt2->indx)
473*38fd1498Szrj {
474*38fd1498Szrj /* We might have advanced beyond the start_bit, so reinitialize
475*38fd1498Szrj for that. */
476*38fd1498Szrj if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
477*38fd1498Szrj start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
478*38fd1498Szrj
479*38fd1498Szrj bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
480*38fd1498Szrj bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
481*38fd1498Szrj bi->bits >>= start_bit % BITMAP_WORD_BITS;
482*38fd1498Szrj }
483*38fd1498Szrj else
484*38fd1498Szrj {
485*38fd1498Szrj /* Otherwise we must immediately advance elt1, so initialize for
486*38fd1498Szrj that. */
487*38fd1498Szrj bi->word_no = BITMAP_ELEMENT_WORDS - 1;
488*38fd1498Szrj bi->bits = 0;
489*38fd1498Szrj }
490*38fd1498Szrj
491*38fd1498Szrj /* If this word is zero, we must make sure we're not pointing at the
492*38fd1498Szrj first bit, otherwise our incrementing to the next word boundary
493*38fd1498Szrj will fail. It won't matter if this increment moves us into the
494*38fd1498Szrj next word. */
495*38fd1498Szrj start_bit += !bi->bits;
496*38fd1498Szrj
497*38fd1498Szrj *bit_no = start_bit;
498*38fd1498Szrj }
499*38fd1498Szrj
500*38fd1498Szrj /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2.
501*38fd1498Szrj */
502*38fd1498Szrj
503*38fd1498Szrj static inline void
bmp_iter_and_compl_init(bitmap_iterator * bi,const_bitmap map1,const_bitmap map2,unsigned start_bit,unsigned * bit_no)504*38fd1498Szrj bmp_iter_and_compl_init (bitmap_iterator *bi,
505*38fd1498Szrj const_bitmap map1, const_bitmap map2,
506*38fd1498Szrj unsigned start_bit, unsigned *bit_no)
507*38fd1498Szrj {
508*38fd1498Szrj bi->elt1 = map1->first;
509*38fd1498Szrj bi->elt2 = map2->first;
510*38fd1498Szrj
511*38fd1498Szrj /* Advance elt1 until it is not before the block containing start_bit. */
512*38fd1498Szrj while (1)
513*38fd1498Szrj {
514*38fd1498Szrj if (!bi->elt1)
515*38fd1498Szrj {
516*38fd1498Szrj bi->elt1 = &bitmap_zero_bits;
517*38fd1498Szrj break;
518*38fd1498Szrj }
519*38fd1498Szrj
520*38fd1498Szrj if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
521*38fd1498Szrj break;
522*38fd1498Szrj bi->elt1 = bi->elt1->next;
523*38fd1498Szrj }
524*38fd1498Szrj
525*38fd1498Szrj /* Advance elt2 until it is not before elt1. */
526*38fd1498Szrj while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
527*38fd1498Szrj bi->elt2 = bi->elt2->next;
528*38fd1498Szrj
529*38fd1498Szrj /* We might have advanced beyond the start_bit, so reinitialize for
530*38fd1498Szrj that. */
531*38fd1498Szrj if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
532*38fd1498Szrj start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
533*38fd1498Szrj
534*38fd1498Szrj bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
535*38fd1498Szrj bi->bits = bi->elt1->bits[bi->word_no];
536*38fd1498Szrj if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
537*38fd1498Szrj bi->bits &= ~bi->elt2->bits[bi->word_no];
538*38fd1498Szrj bi->bits >>= start_bit % BITMAP_WORD_BITS;
539*38fd1498Szrj
540*38fd1498Szrj /* If this word is zero, we must make sure we're not pointing at the
541*38fd1498Szrj first bit, otherwise our incrementing to the next word boundary
542*38fd1498Szrj will fail. It won't matter if this increment moves us into the
543*38fd1498Szrj next word. */
544*38fd1498Szrj start_bit += !bi->bits;
545*38fd1498Szrj
546*38fd1498Szrj *bit_no = start_bit;
547*38fd1498Szrj }
548*38fd1498Szrj
549*38fd1498Szrj /* Advance to the next bit in BI. We don't advance to the next
550*38fd1498Szrj nonzero bit yet. */
551*38fd1498Szrj
552*38fd1498Szrj static inline void
bmp_iter_next(bitmap_iterator * bi,unsigned * bit_no)553*38fd1498Szrj bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
554*38fd1498Szrj {
555*38fd1498Szrj bi->bits >>= 1;
556*38fd1498Szrj *bit_no += 1;
557*38fd1498Szrj }
558*38fd1498Szrj
559*38fd1498Szrj /* Advance to first set bit in BI. */
560*38fd1498Szrj
561*38fd1498Szrj static inline void
bmp_iter_next_bit(bitmap_iterator * bi,unsigned * bit_no)562*38fd1498Szrj bmp_iter_next_bit (bitmap_iterator * bi, unsigned *bit_no)
563*38fd1498Szrj {
564*38fd1498Szrj #if (GCC_VERSION >= 3004)
565*38fd1498Szrj {
566*38fd1498Szrj unsigned int n = __builtin_ctzl (bi->bits);
567*38fd1498Szrj gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
568*38fd1498Szrj bi->bits >>= n;
569*38fd1498Szrj *bit_no += n;
570*38fd1498Szrj }
571*38fd1498Szrj #else
572*38fd1498Szrj while (!(bi->bits & 1))
573*38fd1498Szrj {
574*38fd1498Szrj bi->bits >>= 1;
575*38fd1498Szrj *bit_no += 1;
576*38fd1498Szrj }
577*38fd1498Szrj #endif
578*38fd1498Szrj }
579*38fd1498Szrj
580*38fd1498Szrj /* Advance to the next nonzero bit of a single bitmap, we will have
581*38fd1498Szrj already advanced past the just iterated bit. Return true if there
582*38fd1498Szrj is a bit to iterate. */
583*38fd1498Szrj
584*38fd1498Szrj static inline bool
bmp_iter_set(bitmap_iterator * bi,unsigned * bit_no)585*38fd1498Szrj bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
586*38fd1498Szrj {
587*38fd1498Szrj /* If our current word is nonzero, it contains the bit we want. */
588*38fd1498Szrj if (bi->bits)
589*38fd1498Szrj {
590*38fd1498Szrj next_bit:
591*38fd1498Szrj bmp_iter_next_bit (bi, bit_no);
592*38fd1498Szrj return true;
593*38fd1498Szrj }
594*38fd1498Szrj
595*38fd1498Szrj /* Round up to the word boundary. We might have just iterated past
596*38fd1498Szrj the end of the last word, hence the -1. It is not possible for
597*38fd1498Szrj bit_no to point at the beginning of the now last word. */
598*38fd1498Szrj *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
599*38fd1498Szrj / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
600*38fd1498Szrj bi->word_no++;
601*38fd1498Szrj
602*38fd1498Szrj while (1)
603*38fd1498Szrj {
604*38fd1498Szrj /* Find the next nonzero word in this elt. */
605*38fd1498Szrj while (bi->word_no != BITMAP_ELEMENT_WORDS)
606*38fd1498Szrj {
607*38fd1498Szrj bi->bits = bi->elt1->bits[bi->word_no];
608*38fd1498Szrj if (bi->bits)
609*38fd1498Szrj goto next_bit;
610*38fd1498Szrj *bit_no += BITMAP_WORD_BITS;
611*38fd1498Szrj bi->word_no++;
612*38fd1498Szrj }
613*38fd1498Szrj
614*38fd1498Szrj /* Make sure we didn't remove the element while iterating. */
615*38fd1498Szrj gcc_checking_assert (bi->elt1->indx != -1U);
616*38fd1498Szrj
617*38fd1498Szrj /* Advance to the next element. */
618*38fd1498Szrj bi->elt1 = bi->elt1->next;
619*38fd1498Szrj if (!bi->elt1)
620*38fd1498Szrj return false;
621*38fd1498Szrj *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
622*38fd1498Szrj bi->word_no = 0;
623*38fd1498Szrj }
624*38fd1498Szrj }
625*38fd1498Szrj
626*38fd1498Szrj /* Advance to the next nonzero bit of an intersecting pair of
627*38fd1498Szrj bitmaps. We will have already advanced past the just iterated bit.
628*38fd1498Szrj Return true if there is a bit to iterate. */
629*38fd1498Szrj
630*38fd1498Szrj static inline bool
bmp_iter_and(bitmap_iterator * bi,unsigned * bit_no)631*38fd1498Szrj bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
632*38fd1498Szrj {
633*38fd1498Szrj /* If our current word is nonzero, it contains the bit we want. */
634*38fd1498Szrj if (bi->bits)
635*38fd1498Szrj {
636*38fd1498Szrj next_bit:
637*38fd1498Szrj bmp_iter_next_bit (bi, bit_no);
638*38fd1498Szrj return true;
639*38fd1498Szrj }
640*38fd1498Szrj
641*38fd1498Szrj /* Round up to the word boundary. We might have just iterated past
642*38fd1498Szrj the end of the last word, hence the -1. It is not possible for
643*38fd1498Szrj bit_no to point at the beginning of the now last word. */
644*38fd1498Szrj *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
645*38fd1498Szrj / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
646*38fd1498Szrj bi->word_no++;
647*38fd1498Szrj
648*38fd1498Szrj while (1)
649*38fd1498Szrj {
650*38fd1498Szrj /* Find the next nonzero word in this elt. */
651*38fd1498Szrj while (bi->word_no != BITMAP_ELEMENT_WORDS)
652*38fd1498Szrj {
653*38fd1498Szrj bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
654*38fd1498Szrj if (bi->bits)
655*38fd1498Szrj goto next_bit;
656*38fd1498Szrj *bit_no += BITMAP_WORD_BITS;
657*38fd1498Szrj bi->word_no++;
658*38fd1498Szrj }
659*38fd1498Szrj
660*38fd1498Szrj /* Advance to the next identical element. */
661*38fd1498Szrj do
662*38fd1498Szrj {
663*38fd1498Szrj /* Make sure we didn't remove the element while iterating. */
664*38fd1498Szrj gcc_checking_assert (bi->elt1->indx != -1U);
665*38fd1498Szrj
666*38fd1498Szrj /* Advance elt1 while it is less than elt2. We always want
667*38fd1498Szrj to advance one elt. */
668*38fd1498Szrj do
669*38fd1498Szrj {
670*38fd1498Szrj bi->elt1 = bi->elt1->next;
671*38fd1498Szrj if (!bi->elt1)
672*38fd1498Szrj return false;
673*38fd1498Szrj }
674*38fd1498Szrj while (bi->elt1->indx < bi->elt2->indx);
675*38fd1498Szrj
676*38fd1498Szrj /* Make sure we didn't remove the element while iterating. */
677*38fd1498Szrj gcc_checking_assert (bi->elt2->indx != -1U);
678*38fd1498Szrj
679*38fd1498Szrj /* Advance elt2 to be no less than elt1. This might not
680*38fd1498Szrj advance. */
681*38fd1498Szrj while (bi->elt2->indx < bi->elt1->indx)
682*38fd1498Szrj {
683*38fd1498Szrj bi->elt2 = bi->elt2->next;
684*38fd1498Szrj if (!bi->elt2)
685*38fd1498Szrj return false;
686*38fd1498Szrj }
687*38fd1498Szrj }
688*38fd1498Szrj while (bi->elt1->indx != bi->elt2->indx);
689*38fd1498Szrj
690*38fd1498Szrj *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
691*38fd1498Szrj bi->word_no = 0;
692*38fd1498Szrj }
693*38fd1498Szrj }
694*38fd1498Szrj
695*38fd1498Szrj /* Advance to the next nonzero bit in the intersection of
696*38fd1498Szrj complemented bitmaps. We will have already advanced past the just
697*38fd1498Szrj iterated bit. */
698*38fd1498Szrj
699*38fd1498Szrj static inline bool
bmp_iter_and_compl(bitmap_iterator * bi,unsigned * bit_no)700*38fd1498Szrj bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
701*38fd1498Szrj {
702*38fd1498Szrj /* If our current word is nonzero, it contains the bit we want. */
703*38fd1498Szrj if (bi->bits)
704*38fd1498Szrj {
705*38fd1498Szrj next_bit:
706*38fd1498Szrj bmp_iter_next_bit (bi, bit_no);
707*38fd1498Szrj return true;
708*38fd1498Szrj }
709*38fd1498Szrj
710*38fd1498Szrj /* Round up to the word boundary. We might have just iterated past
711*38fd1498Szrj the end of the last word, hence the -1. It is not possible for
712*38fd1498Szrj bit_no to point at the beginning of the now last word. */
713*38fd1498Szrj *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
714*38fd1498Szrj / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
715*38fd1498Szrj bi->word_no++;
716*38fd1498Szrj
717*38fd1498Szrj while (1)
718*38fd1498Szrj {
719*38fd1498Szrj /* Find the next nonzero word in this elt. */
720*38fd1498Szrj while (bi->word_no != BITMAP_ELEMENT_WORDS)
721*38fd1498Szrj {
722*38fd1498Szrj bi->bits = bi->elt1->bits[bi->word_no];
723*38fd1498Szrj if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
724*38fd1498Szrj bi->bits &= ~bi->elt2->bits[bi->word_no];
725*38fd1498Szrj if (bi->bits)
726*38fd1498Szrj goto next_bit;
727*38fd1498Szrj *bit_no += BITMAP_WORD_BITS;
728*38fd1498Szrj bi->word_no++;
729*38fd1498Szrj }
730*38fd1498Szrj
731*38fd1498Szrj /* Make sure we didn't remove the element while iterating. */
732*38fd1498Szrj gcc_checking_assert (bi->elt1->indx != -1U);
733*38fd1498Szrj
734*38fd1498Szrj /* Advance to the next element of elt1. */
735*38fd1498Szrj bi->elt1 = bi->elt1->next;
736*38fd1498Szrj if (!bi->elt1)
737*38fd1498Szrj return false;
738*38fd1498Szrj
739*38fd1498Szrj /* Make sure we didn't remove the element while iterating. */
740*38fd1498Szrj gcc_checking_assert (! bi->elt2 || bi->elt2->indx != -1U);
741*38fd1498Szrj
742*38fd1498Szrj /* Advance elt2 until it is no less than elt1. */
743*38fd1498Szrj while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
744*38fd1498Szrj bi->elt2 = bi->elt2->next;
745*38fd1498Szrj
746*38fd1498Szrj *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
747*38fd1498Szrj bi->word_no = 0;
748*38fd1498Szrj }
749*38fd1498Szrj }
750*38fd1498Szrj
751*38fd1498Szrj /* If you are modifying a bitmap you are currently iterating over you
752*38fd1498Szrj have to ensure to
753*38fd1498Szrj - never remove the current bit;
754*38fd1498Szrj - if you set or clear a bit before the current bit this operation
755*38fd1498Szrj will not affect the set of bits you are visiting during the iteration;
756*38fd1498Szrj - if you set or clear a bit after the current bit it is unspecified
757*38fd1498Szrj whether that affects the set of bits you are visiting during the
758*38fd1498Szrj iteration.
759*38fd1498Szrj If you want to remove the current bit you can delay this to the next
760*38fd1498Szrj iteration (and after the iteration in case the last iteration is
761*38fd1498Szrj affected). */
762*38fd1498Szrj
763*38fd1498Szrj /* Loop over all bits set in BITMAP, starting with MIN and setting
764*38fd1498Szrj BITNUM to the bit number. ITER is a bitmap iterator. BITNUM
765*38fd1498Szrj should be treated as a read-only variable as it contains loop
766*38fd1498Szrj state. */
767*38fd1498Szrj
768*38fd1498Szrj #ifndef EXECUTE_IF_SET_IN_BITMAP
769*38fd1498Szrj /* See sbitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */
770*38fd1498Szrj #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \
771*38fd1498Szrj for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
772*38fd1498Szrj bmp_iter_set (&(ITER), &(BITNUM)); \
773*38fd1498Szrj bmp_iter_next (&(ITER), &(BITNUM)))
774*38fd1498Szrj #endif
775*38fd1498Szrj
776*38fd1498Szrj /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
777*38fd1498Szrj and setting BITNUM to the bit number. ITER is a bitmap iterator.
778*38fd1498Szrj BITNUM should be treated as a read-only variable as it contains
779*38fd1498Szrj loop state. */
780*38fd1498Szrj
781*38fd1498Szrj #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
782*38fd1498Szrj for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
783*38fd1498Szrj &(BITNUM)); \
784*38fd1498Szrj bmp_iter_and (&(ITER), &(BITNUM)); \
785*38fd1498Szrj bmp_iter_next (&(ITER), &(BITNUM)))
786*38fd1498Szrj
787*38fd1498Szrj /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
788*38fd1498Szrj and setting BITNUM to the bit number. ITER is a bitmap iterator.
789*38fd1498Szrj BITNUM should be treated as a read-only variable as it contains
790*38fd1498Szrj loop state. */
791*38fd1498Szrj
792*38fd1498Szrj #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
793*38fd1498Szrj for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
794*38fd1498Szrj &(BITNUM)); \
795*38fd1498Szrj bmp_iter_and_compl (&(ITER), &(BITNUM)); \
796*38fd1498Szrj bmp_iter_next (&(ITER), &(BITNUM)))
797*38fd1498Szrj
798*38fd1498Szrj /* A class that ties the lifetime of a bitmap to its scope. */
799*38fd1498Szrj class auto_bitmap
800*38fd1498Szrj {
801*38fd1498Szrj public:
auto_bitmap()802*38fd1498Szrj auto_bitmap () { bitmap_initialize (&m_bits, &bitmap_default_obstack); }
auto_bitmap(bitmap_obstack * o)803*38fd1498Szrj explicit auto_bitmap (bitmap_obstack *o) { bitmap_initialize (&m_bits, o); }
~auto_bitmap()804*38fd1498Szrj ~auto_bitmap () { bitmap_clear (&m_bits); }
805*38fd1498Szrj // Allow calling bitmap functions on our bitmap.
bitmap()806*38fd1498Szrj operator bitmap () { return &m_bits; }
807*38fd1498Szrj
808*38fd1498Szrj private:
809*38fd1498Szrj // Prevent making a copy that references our bitmap.
810*38fd1498Szrj auto_bitmap (const auto_bitmap &);
811*38fd1498Szrj auto_bitmap &operator = (const auto_bitmap &);
812*38fd1498Szrj #if __cplusplus >= 201103L
813*38fd1498Szrj auto_bitmap (auto_bitmap &&);
814*38fd1498Szrj auto_bitmap &operator = (auto_bitmap &&);
815*38fd1498Szrj #endif
816*38fd1498Szrj
817*38fd1498Szrj bitmap_head m_bits;
818*38fd1498Szrj };
819*38fd1498Szrj
820*38fd1498Szrj #endif /* GCC_BITMAP_H */
821