1/* Simple bitmaps. 2 Copyright (C) 1999-2015 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. */ 129struct sbitmap_iterator { 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}; 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 debug_raw (const simple_bitmap_def &ref); 227extern void debug_raw (const simple_bitmap_def *ptr); 228extern void dump_bitmap_file (FILE *, const_sbitmap); 229extern void debug (const simple_bitmap_def &ref); 230extern void debug (const simple_bitmap_def *ptr); 231extern void dump_bitmap_vector (FILE *, const char *, const char *, sbitmap *, 232 int); 233extern sbitmap sbitmap_alloc (unsigned int); 234extern sbitmap sbitmap_alloc_with_popcount (unsigned int); 235extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int); 236extern sbitmap sbitmap_resize (sbitmap, unsigned int, int); 237extern void bitmap_copy (sbitmap, const_sbitmap); 238extern int bitmap_equal_p (const_sbitmap, const_sbitmap); 239extern bool bitmap_empty_p (const_sbitmap); 240extern void bitmap_clear (sbitmap); 241extern void bitmap_ones (sbitmap); 242extern void bitmap_vector_clear (sbitmap *, unsigned int); 243extern void bitmap_vector_ones (sbitmap *, unsigned int); 244 245extern bool bitmap_ior_and_compl (sbitmap, const_sbitmap, 246 const_sbitmap, const_sbitmap); 247extern void bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap); 248extern void bitmap_not (sbitmap, const_sbitmap); 249extern bool bitmap_or_and (sbitmap, const_sbitmap, 250 const_sbitmap, const_sbitmap); 251extern bool bitmap_and_or (sbitmap, const_sbitmap, 252 const_sbitmap, const_sbitmap); 253extern bool bitmap_intersect_p (const_sbitmap, const_sbitmap); 254extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap); 255extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap); 256extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap); 257extern bool bitmap_subset_p (const_sbitmap, const_sbitmap); 258 259extern int bitmap_first_set_bit (const_sbitmap); 260extern int bitmap_last_set_bit (const_sbitmap); 261 262extern void debug_bitmap (const_sbitmap); 263extern sbitmap sbitmap_realloc (sbitmap, unsigned int); 264extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long); 265#endif /* ! GCC_SBITMAP_H */ 266