2 Copyright (C) 1999-2012 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
23 /* Implementation of sets using simple bitmap vectors.
25 This set representation is suitable for non-sparse sets with a known
26 (a priori) universe. The set is represented as a simple array of the
27 host's fastest unsigned integer. For a given member I in the set:
28 - the element for I will be at sbitmap[I / (bits per element)]
29 - the position for I within element is I % (bits per element)
31 This representation is very space-efficient for large non-sparse sets
32 with random access patterns.
34 The following operations can be performed in O(1) time:
36 * set_size : SBITMAP_SIZE
38 * add_member : SET_BIT
39 * remove_member : RESET_BIT
41 Most other operations on this set representation are O(U) where U is
42 the size of the set universe:
44 * clear : bitmap_clear
45 * cardinality : sbitmap_popcount
46 * choose_one : bitmap_first_set_bit /
48 * forall : EXECUTE_IF_SET_IN_SBITMAP
49 * set_copy : bitmap_copy / bitmap_copy_n
50 * set_intersection : bitmap_and
51 * set_union : bitmap_ior
52 * set_difference : bitmap_and_compl
53 * set_disjuction : (not implemented)
54 * set_compare : bitmap_equal_p
56 Some operations on 3 sets that occur frequently in in data flow problems
59 * A | (B & C) : bitmap_or_and
60 * A | (B & ~C) : bitmap_ior_and_compl
61 * A & (B | C) : bitmap_and_or
63 Most of the set functions have two variants: One that returns non-zero
64 if members were added or removed from the target set, and one that just
65 performs the operation without feedback. The former operations are a
66 bit more expensive but the result can often be used to avoid iterations
69 Allocating a bitmap is done with sbitmap_alloc, and resizing is
70 performed with sbitmap_resize.
72 The storage requirements for simple bitmap sets is O(U) where U is the
73 size of the set universe (colloquially the number of bits in the bitmap).
75 This set representation works well for relatively small data flow problems
76 (there are special routines for that, see sbitmap_vector_*). The set
77 operations can be vectorized and there is almost no computating overhead,
78 so that even sparse simple bitmap sets outperform dedicated sparse set
79 representations like linked-list bitmaps. For larger problems, the size
80 overhead of simple bitmap sets gets too high and other set representations
83 #define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u)
84 #define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
86 struct simple_bitmap_def
88 unsigned char *popcount
; /* Population count. */
89 unsigned int n_bits
; /* Number of bits. */
90 unsigned int size
; /* Size in elements. */
91 SBITMAP_ELT_TYPE elms
[1]; /* The elements. */
94 /* Return the set size needed for N elements. */
95 #define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
96 #define SBITMAP_SIZE_BYTES(BITMAP) ((BITMAP)->size * sizeof (SBITMAP_ELT_TYPE))
98 /* Return the number of bits in BITMAP. */
99 #define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits)
101 /* Test if bit number bitno in the bitmap is set. */
102 static inline SBITMAP_ELT_TYPE
103 TEST_BIT (const_sbitmap map
, unsigned int bitno
)
105 size_t i
= bitno
/ SBITMAP_ELT_BITS
;
106 unsigned int s
= bitno
% SBITMAP_ELT_BITS
;
107 return (map
->elms
[i
] >> s
) & (SBITMAP_ELT_TYPE
) 1;
110 /* Set bit number BITNO in the sbitmap MAP. */
113 SET_BIT (sbitmap map
, unsigned int bitno
)
115 gcc_checking_assert (! map
->popcount
);
116 map
->elms
[bitno
/ SBITMAP_ELT_BITS
]
117 |= (SBITMAP_ELT_TYPE
) 1 << (bitno
) % SBITMAP_ELT_BITS
;
120 /* Like SET_BIT, but updates population count. */
123 SET_BIT_WITH_POPCOUNT (sbitmap map
, unsigned int bitno
)
126 gcc_checking_assert (map
->popcount
);
127 oldbit
= TEST_BIT (map
, bitno
);
129 map
->popcount
[bitno
/ SBITMAP_ELT_BITS
]++;
130 map
->elms
[bitno
/ SBITMAP_ELT_BITS
]
131 |= (SBITMAP_ELT_TYPE
) 1 << (bitno
) % SBITMAP_ELT_BITS
;
134 /* Reset bit number BITNO in the sbitmap MAP. */
137 RESET_BIT (sbitmap map
, unsigned int bitno
)
139 gcc_checking_assert (! map
->popcount
);
140 map
->elms
[bitno
/ SBITMAP_ELT_BITS
]
141 &= ~((SBITMAP_ELT_TYPE
) 1 << (bitno
) % SBITMAP_ELT_BITS
);
144 /* Like RESET_BIT, but updates population count. */
147 RESET_BIT_WITH_POPCOUNT (sbitmap map
, unsigned int bitno
)
150 gcc_checking_assert (map
->popcount
);
151 oldbit
= TEST_BIT (map
, bitno
);
153 map
->popcount
[bitno
/ SBITMAP_ELT_BITS
]--;
154 map
->elms
[bitno
/ SBITMAP_ELT_BITS
]
155 &= ~((SBITMAP_ELT_TYPE
) 1 << (bitno
) % SBITMAP_ELT_BITS
);
158 /* The iterator for sbitmap. */
160 /* The pointer to the first word of the bitmap. */
161 const SBITMAP_ELT_TYPE
*ptr
;
163 /* The size of the bitmap. */
166 /* The current word index. */
167 unsigned int word_num
;
169 /* The current bit index (not modulo SBITMAP_ELT_BITS). */
170 unsigned int bit_num
;
172 /* The words currently visited. */
173 SBITMAP_ELT_TYPE word
;
176 /* Initialize the iterator I with sbitmap BMP and the initial index
180 sbitmap_iter_init (sbitmap_iterator
*i
, const_sbitmap bmp
, unsigned int min
)
182 i
->word_num
= min
/ (unsigned int) SBITMAP_ELT_BITS
;
187 if (i
->word_num
>= i
->size
)
190 i
->word
= (i
->ptr
[i
->word_num
]
191 >> (i
->bit_num
% (unsigned int) SBITMAP_ELT_BITS
));
194 /* Return true if we have more bits to visit, in which case *N is set
195 to the index of the bit to be visited. Otherwise, return
199 sbitmap_iter_cond (sbitmap_iterator
*i
, unsigned int *n
)
201 /* Skip words that are zeros. */
202 for (; i
->word
== 0; i
->word
= i
->ptr
[i
->word_num
])
206 /* If we have reached the end, break. */
207 if (i
->word_num
>= i
->size
)
210 i
->bit_num
= i
->word_num
* SBITMAP_ELT_BITS
;
213 /* Skip bits that are zero. */
214 for (; (i
->word
& 1) == 0; i
->word
>>= 1)
222 /* Advance to the next bit. */
225 sbitmap_iter_next (sbitmap_iterator
*i
)
231 /* Loop over all elements of SBITMAP, starting with MIN. In each
232 iteration, N is set to the index of the bit being visited. ITER is
233 an instance of sbitmap_iterator used to iterate the bitmap. */
235 #define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, ITER) \
236 for (sbitmap_iter_init (&(ITER), (SBITMAP), (MIN)); \
237 sbitmap_iter_cond (&(ITER), &(N)); \
238 sbitmap_iter_next (&(ITER)))
240 #define EXECUTE_IF_SET_IN_SBITMAP_REV(SBITMAP, N, CODE) \
242 unsigned int word_num_; \
243 unsigned int bit_num_; \
244 unsigned int size_ = (SBITMAP)->size; \
245 SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \
247 for (word_num_ = size_; word_num_ > 0; word_num_--) \
249 SBITMAP_ELT_TYPE word_ = ptr_[word_num_ - 1]; \
252 for (bit_num_ = SBITMAP_ELT_BITS; bit_num_ > 0; bit_num_--) \
254 SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE)1 << (bit_num_ - 1);\
256 if ((word_ & _mask) != 0) \
259 (N) = (word_num_ - 1) * SBITMAP_ELT_BITS + bit_num_ - 1;\
268 inline void sbitmap_free (sbitmap map
)
270 free (map
->popcount
);
274 inline void sbitmap_vector_free (sbitmap
* vec
)
279 extern void dump_bitmap (FILE *, const_sbitmap
);
280 extern void dump_bitmap_file (FILE *, const_sbitmap
);
281 extern void dump_bitmap_vector (FILE *, const char *, const char *, sbitmap
*,
283 extern sbitmap
sbitmap_alloc (unsigned int);
284 extern sbitmap
sbitmap_alloc_with_popcount (unsigned int);
285 extern sbitmap
*sbitmap_vector_alloc (unsigned int, unsigned int);
286 extern sbitmap
sbitmap_resize (sbitmap
, unsigned int, int);
287 extern void bitmap_copy (sbitmap
, const_sbitmap
);
288 extern void bitmap_copy_n (sbitmap
, const_sbitmap
, unsigned int);
289 extern int bitmap_equal_p (const_sbitmap
, const_sbitmap
);
290 extern bool bitmap_empty_p (const_sbitmap
);
291 extern bool bitmap_range_empty_p (const_sbitmap
, unsigned int, unsigned int);
292 extern void bitmap_clear (sbitmap
);
293 extern void bitmap_ones (sbitmap
);
294 extern void bitmap_vector_clear (sbitmap
*, unsigned int);
295 extern void bitmap_vector_ones (sbitmap
*, unsigned int);
297 extern bool bitmap_ior_and_compl (sbitmap
, const_sbitmap
,
298 const_sbitmap
, const_sbitmap
);
299 extern void bitmap_and_compl (sbitmap
, const_sbitmap
, const_sbitmap
);
300 extern void bitmap_not (sbitmap
, const_sbitmap
);
301 extern bool bitmap_or_and (sbitmap
, const_sbitmap
,
302 const_sbitmap
, const_sbitmap
);
303 extern bool bitmap_and_or (sbitmap
, const_sbitmap
,
304 const_sbitmap
, const_sbitmap
);
305 extern bool bitmap_intersect_p (const_sbitmap
, const_sbitmap
);
306 extern bool bitmap_and (sbitmap
, const_sbitmap
, const_sbitmap
);
307 extern bool bitmap_ior (sbitmap
, const_sbitmap
, const_sbitmap
);
308 extern bool bitmap_xor (sbitmap
, const_sbitmap
, const_sbitmap
);
309 extern bool bitmap_subset_p (const_sbitmap
, const_sbitmap
);
311 extern int bitmap_first_set_bit (const_sbitmap
);
312 extern int bitmap_last_set_bit (const_sbitmap
);
314 extern void debug_bitmap (const_sbitmap
);
315 extern sbitmap
sbitmap_realloc (sbitmap
, unsigned int);
316 extern unsigned long sbitmap_popcount (const_sbitmap
, unsigned long);
317 extern void sbitmap_verify_popcount (const_sbitmap
);
318 #endif /* ! GCC_SBITMAP_H */