gcc/sbitmap.h

   1 /* Simple bitmaps.
   2    Copyright (C) 1999-2012  Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   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
   9 version.
  10
  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
  14 for more details.
  15
  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/>.  */
  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                 : TEST_BIT
  38      * add_member               : SET_BIT
  39      * remove_member            : RESET_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                    : sbitmap_zero
  45      * cardinality              : sbitmap_popcount
  46      * choose_one               : sbitmap_first_set_bit /
  47                                   sbitmap_last_set_bit
  48      * forall                   : EXECUTE_IF_SET_IN_SBITMAP
  49      * set_copy                 : sbitmap_copy / sbitmap_copy_n
  50      * set_intersection         : sbitmap_a_and_b
  51      * set_union                : sbitmap_a_or_b
  52      * set_difference           : sbitmap_difference
  53      * set_disjuction           : (not implemented)
  54      * set_compare              : sbitmap_equal
  55
  56    Some operations on 3 sets that occur frequently in in data flow problems
  57    are also implemented:
  58
  59       * A | (B & C)             : sbitmap_a_or_b_and_c
  60       * A | (B & ~C)            : sbitmap_union_of_diff
  61       * A & (B | C)             : sbitmap_a_and_b_or_c
  62
  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
  67    on other sets.
  68
  69    Allocating a bitmap is done with sbitmap_alloc, and resizing is
  70    performed with sbitmap_resize.
  71
  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).
  74
  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
  81    have to be used.  */
  82
  83 #define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u)
  84 #define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
  85
  86 struct simple_bitmap_def
  87 {
  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.  */
  92 };
  93
  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))
  97
  98 /* Return the number of bits in BITMAP.  */
  99 #define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits)
 100
 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)
 104 {
 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;
 108 }
 109
 110 /* Set bit number BITNO in the sbitmap MAP.  */
 111
 112 static inline void
 113 SET_BIT (sbitmap map, unsigned int bitno)
 114 {
 115   gcc_checking_assert (! map->popcount);
 116   map->elms[bitno / SBITMAP_ELT_BITS]
 117     |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
 118 }
 119
 120 /* Like SET_BIT, but updates population count.  */
 121
 122 static inline void
 123 SET_BIT_WITH_POPCOUNT (sbitmap map, unsigned int bitno)
 124 {
 125   bool oldbit;
 126   gcc_checking_assert (map->popcount);
 127   oldbit = TEST_BIT (map, bitno);
 128   if (!oldbit)
 129     map->popcount[bitno / SBITMAP_ELT_BITS]++;
 130   map->elms[bitno / SBITMAP_ELT_BITS]
 131     |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
 132 }
 133
 134 /* Reset bit number BITNO in the sbitmap MAP.  */
 135
 136 static inline void
 137 RESET_BIT (sbitmap map,  unsigned int bitno)
 138 {
 139   gcc_checking_assert (! map->popcount);
 140   map->elms[bitno / SBITMAP_ELT_BITS]
 141     &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
 142 }
 143
 144 /* Like RESET_BIT, but updates population count.  */
 145
 146 static inline void
 147 RESET_BIT_WITH_POPCOUNT (sbitmap map,  unsigned int bitno)
 148 {
 149   bool oldbit;
 150   gcc_checking_assert (map->popcount);
 151   oldbit = TEST_BIT (map, bitno);
 152   if (oldbit)
 153     map->popcount[bitno / SBITMAP_ELT_BITS]--;
 154   map->elms[bitno / SBITMAP_ELT_BITS]
 155     &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
 156 }
 157
 158 /* The iterator for sbitmap.  */
 159 typedef struct {
 160   /* The pointer to the first word of the bitmap.  */
 161   const SBITMAP_ELT_TYPE *ptr;
 162
 163   /* The size of the bitmap.  */
 164   unsigned int size;
 165
 166   /* The current word index.  */
 167   unsigned int word_num;
 168
 169   /* The current bit index (not modulo SBITMAP_ELT_BITS).  */
 170   unsigned int bit_num;
 171
 172   /* The words currently visited.  */
 173   SBITMAP_ELT_TYPE word;
 174 } sbitmap_iterator;
 175
 176 /* Initialize the iterator I with sbitmap BMP and the initial index
 177    MIN.  */
 178
 179 static inline void
 180 sbitmap_iter_init (sbitmap_iterator *i, const_sbitmap bmp, unsigned int min)
 181 {
 182   i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
 183   i->bit_num = min;
 184   i->size = bmp->size;
 185   i->ptr = bmp->elms;
 186
 187   if (i->word_num >= i->size)
 188     i->word = 0;
 189   else
 190     i->word = (i->ptr[i->word_num]
 191                >> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
 192 }
 193
 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
 196    false.  */
 197
 198 static inline bool
 199 sbitmap_iter_cond (sbitmap_iterator *i, unsigned int *n)
 200 {
 201   /* Skip words that are zeros.  */
 202   for (; i->word == 0; i->word = i->ptr[i->word_num])
 203     {
 204       i->word_num++;
 205
 206       /* If we have reached the end, break.  */
 207       if (i->word_num >= i->size)
 208         return false;
 209
 210       i->bit_num = i->word_num * SBITMAP_ELT_BITS;
 211     }
 212
 213   /* Skip bits that are zero.  */
 214   for (; (i->word & 1) == 0; i->word >>= 1)
 215     i->bit_num++;
 216
 217   *n = i->bit_num;
 218
 219   return true;
 220 }
 221
 222 /* Advance to the next bit.  */
 223
 224 static inline void
 225 sbitmap_iter_next (sbitmap_iterator *i)
 226 {
 227   i->word >>= 1;
 228   i->bit_num++;
 229 }
 230
 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.  */
 234
 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)))
 239
 240 #define EXECUTE_IF_SET_IN_SBITMAP_REV(SBITMAP, N, CODE)                 \
 241 do {                                                                    \
 242   unsigned int word_num_;                                               \
 243   unsigned int bit_num_;                                                \
 244   unsigned int size_ = (SBITMAP)->size;                                 \
 245   SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms;                             \
 246                                                                         \
 247   for (word_num_ = size_; word_num_ > 0; word_num_--)                   \
 248     {                                                                   \
 249       SBITMAP_ELT_TYPE word_ = ptr_[word_num_ - 1];                     \
 250                                                                         \
 251       if (word_ != 0)                                                   \
 252         for (bit_num_ = SBITMAP_ELT_BITS; bit_num_ > 0; bit_num_--)     \
 253           {                                                             \
 254             SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE)1 << (bit_num_ - 1);\
 255                                                                         \
 256             if ((word_ & _mask) != 0)                                   \
 257               {                                                         \
 258                 word_ &= ~ _mask;                                       \
 259                 (N) = (word_num_ - 1) * SBITMAP_ELT_BITS + bit_num_ - 1;\
 260                 CODE;                                                   \
 261                 if (word_ == 0)                                         \
 262                   break;                                                \
 263               }                                                         \
 264           }                                                             \
 265     }                                                                   \
 266 } while (0)
 267
 268 #define sbitmap_free(MAP)               (free((MAP)->popcount), free((MAP)))
 269 #define sbitmap_vector_free(VEC)        free(VEC)
 270
 271 extern void dump_sbitmap (FILE *, const_sbitmap);
 272 extern void dump_sbitmap_file (FILE *, const_sbitmap);
 273 extern void dump_sbitmap_vector (FILE *, const char *, const char *, sbitmap *,
 274                                  int);
 275 extern sbitmap sbitmap_alloc (unsigned int);
 276 extern sbitmap sbitmap_alloc_with_popcount (unsigned int);
 277 extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
 278 extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
 279 extern void sbitmap_copy (sbitmap, const_sbitmap);
 280 extern void sbitmap_copy_n (sbitmap, const_sbitmap, unsigned int);
 281 extern int sbitmap_equal (const_sbitmap, const_sbitmap);
 282 extern bool sbitmap_empty_p (const_sbitmap);
 283 extern bool sbitmap_range_empty_p (const_sbitmap, unsigned int, unsigned int);
 284 extern void sbitmap_zero (sbitmap);
 285 extern void sbitmap_ones (sbitmap);
 286 extern void sbitmap_vector_zero (sbitmap *, unsigned int);
 287 extern void sbitmap_vector_ones (sbitmap *, unsigned int);
 288
 289 extern void sbitmap_union_of_diff (sbitmap, const_sbitmap,
 290                                    const_sbitmap, const_sbitmap);
 291 extern bool sbitmap_union_of_diff_cg (sbitmap, const_sbitmap,
 292                                       const_sbitmap, const_sbitmap);
 293 extern void sbitmap_difference (sbitmap, const_sbitmap, const_sbitmap);
 294 extern void sbitmap_not (sbitmap, const_sbitmap);
 295 extern void sbitmap_a_or_b_and_c (sbitmap, const_sbitmap,
 296                                   const_sbitmap, const_sbitmap);
 297 extern bool sbitmap_a_or_b_and_c_cg (sbitmap, const_sbitmap,
 298                                      const_sbitmap, const_sbitmap);
 299 extern void sbitmap_a_and_b_or_c (sbitmap, const_sbitmap,
 300                                   const_sbitmap, const_sbitmap);
 301 extern bool sbitmap_a_and_b_or_c_cg (sbitmap, const_sbitmap,
 302                                      const_sbitmap, const_sbitmap);
 303 extern bool sbitmap_any_common_bits (const_sbitmap, const_sbitmap);
 304 extern void sbitmap_a_and_b (sbitmap, const_sbitmap, const_sbitmap);
 305 extern bool sbitmap_a_and_b_cg (sbitmap, const_sbitmap, const_sbitmap);
 306 extern void sbitmap_a_or_b (sbitmap, const_sbitmap, const_sbitmap);
 307 extern bool sbitmap_a_or_b_cg (sbitmap, const_sbitmap, const_sbitmap);
 308 extern void sbitmap_a_xor_b (sbitmap, const_sbitmap, const_sbitmap);
 309 extern bool sbitmap_a_xor_b_cg (sbitmap, const_sbitmap, const_sbitmap);
 310 extern bool sbitmap_a_subset_b_p (const_sbitmap, const_sbitmap);
 311
 312 extern int sbitmap_first_set_bit (const_sbitmap);
 313 extern int sbitmap_last_set_bit (const_sbitmap);
 314
 315 extern void debug_sbitmap (const_sbitmap);
 316 extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
 317 extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long);
 318 extern void sbitmap_verify_popcount (const_sbitmap);
 319 #endif /* ! GCC_SBITMAP_H */