1/* Simple bitmaps. 2 Copyright (C) 1999-2013 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING3. If not see 18<http://www.gnu.org/licenses/>. */ 19 20#ifndef GCC_SBITMAP_H 21#define GCC_SBITMAP_H 22 23/* Implementation of sets using simple bitmap vectors. 24 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) 30 31 This representation is very space-efficient for large non-sparse sets 32 with random access patterns. 33 34 The following operations can be performed in O(1) time: 35 36 * set_size : SBITMAP_SIZE 37 * member_p : bitmap_bit_p 38 * add_member : bitmap_set_bit 39 * remove_member : bitmap_clear_bit 40 41 Most other operations on this set representation are O(U) where U is 42 the size of the set universe: 43 44 * clear : bitmap_clear 45 * choose_one : bitmap_first_set_bit / 46 bitmap_last_set_bit 47 * forall : EXECUTE_IF_SET_IN_BITMAP 48 * set_copy : bitmap_copy 49 * set_intersection : bitmap_and 50 * set_union : bitmap_ior 51 * set_difference : bitmap_and_compl 52 * set_disjuction : (not implemented) 53 * set_compare : bitmap_equal_p 54 55 Some operations on 3 sets that occur frequently in in data flow problems 56 are also implemented: 57 58 * A | (B & C) : bitmap_or_and 59 * A | (B & ~C) : bitmap_ior_and_compl 60 * A & (B | C) : bitmap_and_or 61 62 Most of the set functions have two variants: One that returns non-zero 63 if members were added or removed from the target set, and one that just 64 performs the operation without feedback. The former operations are a 65 bit more expensive but the result can often be used to avoid iterations 66 on other sets. 67 68 Allocating a bitmap is done with sbitmap_alloc, and resizing is 69 performed with sbitmap_resize. 70 71 The storage requirements for simple bitmap sets is O(U) where U is the 72 size of the set universe (colloquially the number of bits in the bitmap). 73 74 This set representation works well for relatively small data flow problems 75 (there are special routines for that, see sbitmap_vector_*). The set 76 operations can be vectorized and there is almost no computating overhead, 77 so that even sparse simple bitmap sets outperform dedicated sparse set 78 representations like linked-list bitmaps. For larger problems, the size 79 overhead of simple bitmap sets gets too high and other set representations 80 have to be used. */ 81 82#define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u) 83#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT 84 85struct simple_bitmap_def 86{ 87 unsigned char *popcount; /* Population count. */ 88 unsigned int n_bits; /* Number of bits. */ 89 unsigned int size; /* Size in elements. */ 90 SBITMAP_ELT_TYPE elms[1]; /* The elements. */ 91}; 92 93/* Return the set size needed for N elements. */ 94#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS) 95 96/* Return the number of bits in BITMAP. */ 97#define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits) 98 99/* Test if bit number bitno in the bitmap is set. */ 100static inline SBITMAP_ELT_TYPE 101bitmap_bit_p (const_sbitmap map, int bitno) 102{ 103 size_t i = bitno / SBITMAP_ELT_BITS; 104 unsigned int s = bitno % SBITMAP_ELT_BITS; 105 return (map->elms[i] >> s) & (SBITMAP_ELT_TYPE) 1; 106} 107 108/* Set bit number BITNO in the sbitmap MAP. */ 109 110static inline void 111bitmap_set_bit (sbitmap map, int bitno) 112{ 113 gcc_checking_assert (! map->popcount); 114 map->elms[bitno / SBITMAP_ELT_BITS] 115 |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS; 116} 117 118/* Reset bit number BITNO in the sbitmap MAP. */ 119 120static inline void 121bitmap_clear_bit (sbitmap map, int bitno) 122{ 123 gcc_checking_assert (! map->popcount); 124 map->elms[bitno / SBITMAP_ELT_BITS] 125 &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS); 126} 127 128/* The iterator for sbitmap. */ 129typedef struct { 130 /* The pointer to the first word of the bitmap. */ 131 const SBITMAP_ELT_TYPE *ptr; 132 133 /* The size of the bitmap. */ 134 unsigned int size; 135 136 /* The current word index. */ 137 unsigned int word_num; 138 139 /* The current bit index (not modulo SBITMAP_ELT_BITS). */ 140 unsigned int bit_num; 141 142 /* The words currently visited. */ 143 SBITMAP_ELT_TYPE word; 144} sbitmap_iterator; 145 146/* Initialize the iterator I with sbitmap BMP and the initial index 147 MIN. */ 148 149static inline void 150bmp_iter_set_init (sbitmap_iterator *i, const_sbitmap bmp, 151 unsigned int min, unsigned *bit_no ATTRIBUTE_UNUSED) 152{ 153 i->word_num = min / (unsigned int) SBITMAP_ELT_BITS; 154 i->bit_num = min; 155 i->size = bmp->size; 156 i->ptr = bmp->elms; 157 158 if (i->word_num >= i->size) 159 i->word = 0; 160 else 161 i->word = (i->ptr[i->word_num] 162 >> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS)); 163} 164 165/* Return true if we have more bits to visit, in which case *N is set 166 to the index of the bit to be visited. Otherwise, return 167 false. */ 168 169static inline bool 170bmp_iter_set (sbitmap_iterator *i, unsigned int *n) 171{ 172 /* Skip words that are zeros. */ 173 for (; i->word == 0; i->word = i->ptr[i->word_num]) 174 { 175 i->word_num++; 176 177 /* If we have reached the end, break. */ 178 if (i->word_num >= i->size) 179 return false; 180 181 i->bit_num = i->word_num * SBITMAP_ELT_BITS; 182 } 183 184 /* Skip bits that are zero. */ 185 for (; (i->word & 1) == 0; i->word >>= 1) 186 i->bit_num++; 187 188 *n = i->bit_num; 189 190 return true; 191} 192 193/* Advance to the next bit. */ 194 195static inline void 196bmp_iter_next (sbitmap_iterator *i, unsigned *bit_no ATTRIBUTE_UNUSED) 197{ 198 i->word >>= 1; 199 i->bit_num++; 200} 201 202/* Loop over all elements of SBITMAP, starting with MIN. In each 203 iteration, N is set to the index of the bit being visited. ITER is 204 an instance of sbitmap_iterator used to iterate the bitmap. */ 205 206#ifndef EXECUTE_IF_SET_IN_BITMAP 207/* See bitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */ 208#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \ 209 for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \ 210 bmp_iter_set (&(ITER), &(BITNUM)); \ 211 bmp_iter_next (&(ITER), &(BITNUM))) 212#endif 213 214inline void sbitmap_free (sbitmap map) 215{ 216 free (map->popcount); 217 free (map); 218} 219 220inline void sbitmap_vector_free (sbitmap * vec) 221{ 222 free (vec); 223} 224 225extern void dump_bitmap (FILE *, const_sbitmap); 226extern void dump_bitmap_file (FILE *, const_sbitmap); 227extern void dump_bitmap_vector (FILE *, const char *, const char *, sbitmap *, 228 int); 229extern sbitmap sbitmap_alloc (unsigned int); 230extern sbitmap sbitmap_alloc_with_popcount (unsigned int); 231extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int); 232extern sbitmap sbitmap_resize (sbitmap, unsigned int, int); 233extern void bitmap_copy (sbitmap, const_sbitmap); 234extern int bitmap_equal_p (const_sbitmap, const_sbitmap); 235extern bool bitmap_empty_p (const_sbitmap); 236extern void bitmap_clear (sbitmap); 237extern void bitmap_ones (sbitmap); 238extern void bitmap_vector_clear (sbitmap *, unsigned int); 239extern void bitmap_vector_ones (sbitmap *, unsigned int); 240 241extern bool bitmap_ior_and_compl (sbitmap, const_sbitmap, 242 const_sbitmap, const_sbitmap); 243extern void bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap); 244extern void bitmap_not (sbitmap, const_sbitmap); 245extern bool bitmap_or_and (sbitmap, const_sbitmap, 246 const_sbitmap, const_sbitmap); 247extern bool bitmap_and_or (sbitmap, const_sbitmap, 248 const_sbitmap, const_sbitmap); 249extern bool bitmap_intersect_p (const_sbitmap, const_sbitmap); 250extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap); 251extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap); 252extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap); 253extern bool bitmap_subset_p (const_sbitmap, const_sbitmap); 254 255extern int bitmap_first_set_bit (const_sbitmap); 256extern int bitmap_last_set_bit (const_sbitmap); 257 258extern void debug_bitmap (const_sbitmap); 259extern sbitmap sbitmap_realloc (sbitmap, unsigned int); 260extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long); 261#endif /* ! GCC_SBITMAP_H */ 262