gcc/bitmap.h

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999, 2000, 2001 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #ifndef GCC_BITMAP_H
  22 #define GCC_BITMAP_H
  23
  24 /* Number of words to use for each element in the linked list.  */
  25
  26 #ifndef BITMAP_ELEMENT_WORDS
  27 #define BITMAP_ELEMENT_WORDS 2
  28 #endif
  29
  30 /* Number of bits in each actual element of a bitmap.  We get slightly better
  31    code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if
  32    bits is unsigned, assuming it is a power of 2.  */
  33
  34 #define BITMAP_ELEMENT_ALL_BITS \
  35   ((unsigned) (BITMAP_ELEMENT_WORDS * HOST_BITS_PER_WIDE_INT))
  36
  37 /* Bitmap set element.  We use a linked list to hold only the bits that
  38    are set.  This allows for use to grow the bitset dynamically without
  39    having to realloc and copy a giant bit array.  The `prev' field is
  40    undefined for an element on the free list.  */
  41
  42 typedef struct bitmap_element_def
  43 {
  44   struct bitmap_element_def *next;              /* Next element.  */
  45   struct bitmap_element_def *prev;              /* Previous element.  */
  46   unsigned int indx;                    /* regno/BITMAP_ELEMENT_ALL_BITS.  */
  47   unsigned HOST_WIDE_INT bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set.  */
  48 } bitmap_element;
  49
  50 /* Head of bitmap linked list.  */
  51 typedef struct bitmap_head_def {
  52   bitmap_element *first;        /* First element in linked list.  */
  53   bitmap_element *current;      /* Last element looked at.  */
  54   unsigned int indx;            /* Index of last element looked at.  */
  55
  56 } bitmap_head, *bitmap;
  57
  58 /* Enumeration giving the various operations we support.  */
  59 enum bitmap_bits {
  60   BITMAP_AND,                   /* TO = FROM1 & FROM2 */
  61   BITMAP_AND_COMPL,             /* TO = FROM1 & ~ FROM2 */
  62   BITMAP_IOR,                   /* TO = FROM1 | FROM2 */
  63   BITMAP_XOR,                   /* TO = FROM1 ^ FROM2 */
  64   BITMAP_IOR_COMPL                      /* TO = FROM1 | ~FROM2 */
  65 };
  66
  67 /* Global data */
  68 extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
  69
  70 /* Clear a bitmap by freeing up the linked list.  */
  71 extern void bitmap_clear PARAMS ((bitmap));
  72
  73 /* Copy a bitmap to another bitmap.  */
  74 extern void bitmap_copy PARAMS ((bitmap, bitmap));
  75
  76 /* True if two bitmaps are identical.  */
  77 extern int bitmap_equal_p PARAMS ((bitmap, bitmap));
  78
  79 /* Perform an operation on two bitmaps, yielding a third.  */
  80 extern int bitmap_operation PARAMS ((bitmap, bitmap, bitmap, enum bitmap_bits));
  81
  82 /* `or' into one bitmap the `and' of a second bitmap witih the complement
  83    of a third.  */
  84 extern void bitmap_ior_and_compl PARAMS ((bitmap, bitmap, bitmap));
  85
  86 /* Clear a single register in a register set.  */
  87 extern void bitmap_clear_bit PARAMS ((bitmap, int));
  88
  89 /* Set a single register in a register set.  */
  90 extern void bitmap_set_bit PARAMS ((bitmap, int));
  91
  92 /* Return true if a register is set in a register set.  */
  93 extern int bitmap_bit_p PARAMS ((bitmap, int));
  94
  95 /* Debug functions to print a bitmap linked list.  */
  96 extern void debug_bitmap PARAMS ((bitmap));
  97 extern void debug_bitmap_file PARAMS ((FILE *, bitmap));
  98
  99 /* Print a bitmap */
 100 extern void bitmap_print PARAMS ((FILE *, bitmap, const char *, const char *));
 101
 102 /* Initialize a bitmap header.  */
 103 extern bitmap bitmap_initialize PARAMS ((bitmap));
 104
 105 /* Release all memory held by bitmaps.  */
 106 extern void bitmap_release_memory PARAMS ((void));
 107
 108 /* A few compatibility/functions macros for compatibility with sbitmaps */
 109 #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
 110 #define bitmap_zero(a) bitmap_clear (a)
 111 #define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR)
 112 #define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND)
 113 extern int bitmap_union_of_diff PARAMS((bitmap, bitmap, bitmap, bitmap));
 114 extern int bitmap_first_set_bit PARAMS((bitmap));
 115 extern int bitmap_last_set_bit PARAMS((bitmap));
 116
 117 /* Allocate a bitmap with oballoc.  */
 118 #define BITMAP_OBSTACK_ALLOC(OBSTACK)                           \
 119   bitmap_initialize ((bitmap) obstack_alloc (OBSTACK, sizeof (bitmap_head)))
 120
 121 /* Allocate a bitmap with alloca.  Note alloca cannot be passed as an
 122    argument to a function, so we set a temporary variable to the value
 123    returned by alloca and pass that variable to bitmap_initialize().
 124    PTR is then set to the value returned from bitmap_initialize() to
 125    avoid having it appear more than once in case it has side effects.  */
 126 #define BITMAP_ALLOCA(PTR) \
 127 do { \
 128   bitmap temp_bitmap_ = (bitmap) alloca (sizeof (bitmap_head)); \
 129   (PTR) = bitmap_initialize (temp_bitmap_); \
 130 } while (0)
 131
 132 /* Allocate a bitmap with xmalloc.  */
 133 #define BITMAP_XMALLOC()                                        \
 134   bitmap_initialize ((bitmap) xmalloc (sizeof (bitmap_head)))
 135
 136 /* Do any cleanup needed on a bitmap when it is no longer used.  */
 137 #define BITMAP_FREE(BITMAP)                     \
 138 do {                                            \
 139   if (BITMAP)                                   \
 140     {                                           \
 141       bitmap_clear (BITMAP);                    \
 142       (BITMAP) = 0;                             \
 143     }                                           \
 144 } while (0)
 145
 146 /* Do any cleanup needed on an xmalloced bitmap when it is no longer used.  */
 147 #define BITMAP_XFREE(BITMAP)                    \
 148 do {                                            \
 149   if (BITMAP)                                   \
 150     {                                           \
 151       bitmap_clear (BITMAP);                    \
 152       free (BITMAP);                            \
 153       (BITMAP) = 0;                             \
 154     }                                           \
 155 } while (0)
 156
 157 /* Do any one-time initializations needed for bitmaps.  */
 158 #define BITMAP_INIT_ONCE()
 159
 160 /* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the
 161    bit number and executing CODE for all bits that are set.  */
 162
 163 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE)             \
 164 do {                                                                    \
 165   bitmap_element *ptr_ = (BITMAP)->first;                               \
 166   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 167   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 168   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 169                         % BITMAP_ELEMENT_WORDS);                        \
 170                                                                         \
 171                                                                         \
 172   /* Find the block the minimum bit is in.  */                          \
 173   while (ptr_ != 0 && ptr_->indx < indx_)                               \
 174     ptr_ = ptr_->next;                                                  \
 175                                                                         \
 176   if (ptr_ != 0 && ptr_->indx != indx_)                                 \
 177     {                                                                   \
 178       bit_num_ = 0;                                                     \
 179       word_num_ = 0;                                                    \
 180     }                                                                   \
 181                                                                         \
 182   for (; ptr_ != 0; ptr_ = ptr_->next)                                  \
 183     {                                                                   \
 184       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 185         {                                                               \
 186           unsigned HOST_WIDE_INT word_ = ptr_->bits[word_num_];         \
 187                                                                         \
 188           if (word_ != 0)                                               \
 189             {                                                           \
 190               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 191                 {                                                       \
 192                   unsigned HOST_WIDE_INT mask_                          \
 193                     = ((unsigned HOST_WIDE_INT) 1) << bit_num_;         \
 194                                                                         \
 195                   if ((word_ & mask_) != 0)                             \
 196                     {                                                   \
 197                       word_ &= ~ mask_;                                 \
 198                       (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS  \
 199                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 200                                   + bit_num_);                          \
 201                       CODE;                                             \
 202                                                                         \
 203                       if (word_ == 0)                                   \
 204                         break;                                          \
 205                     }                                                   \
 206                 }                                                       \
 207             }                                                           \
 208                                                                         \
 209           bit_num_ = 0;                                                 \
 210         }                                                               \
 211                                                                         \
 212       word_num_ = 0;                                                    \
 213     }                                                                   \
 214 } while (0)
 215
 216 /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
 217    BITNUM to the bit number and executing CODE for all bits that are set in
 218    the first bitmap and not set in the second.  */
 219
 220 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \
 221 do {                                                                    \
 222   bitmap_element *ptr1_ = (BITMAP1)->first;                             \
 223   bitmap_element *ptr2_ = (BITMAP2)->first;                             \
 224   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 225   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 226   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 227                         % BITMAP_ELEMENT_WORDS);                        \
 228                                                                         \
 229   /* Find the block the minimum bit is in in the first bitmap.  */      \
 230   while (ptr1_ != 0 && ptr1_->indx < indx_)                             \
 231     ptr1_ = ptr1_->next;                                                \
 232                                                                         \
 233   if (ptr1_ != 0 && ptr1_->indx != indx_)                               \
 234     {                                                                   \
 235       bit_num_ = 0;                                                     \
 236       word_num_ = 0;                                                    \
 237     }                                                                   \
 238                                                                         \
 239   for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)                              \
 240     {                                                                   \
 241       /* Advance BITMAP2 to the equivalent link, using an all           \
 242          zero element if an equivalent link doesn't exist.  */          \
 243       bitmap_element *tmp2_;                                            \
 244                                                                         \
 245       while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)                   \
 246         ptr2_ = ptr2_->next;                                            \
 247                                                                         \
 248       tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx)               \
 249                ? ptr2_ : &bitmap_zero_bits);                            \
 250                                                                         \
 251       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 252         {                                                               \
 253           unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]        \
 254                                           & ~ tmp2_->bits[word_num_]);  \
 255           if (word_ != 0)                                               \
 256             {                                                           \
 257               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 258                 {                                                       \
 259                   unsigned HOST_WIDE_INT mask_                          \
 260                     = ((unsigned HOST_WIDE_INT)1) << bit_num_;          \
 261                                                                         \
 262                   if ((word_ & mask_) != 0)                             \
 263                     {                                                   \
 264                       word_ &= ~ mask_;                                 \
 265                       (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
 266                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 267                                   + bit_num_);                          \
 268                                                                         \
 269                       CODE;                                             \
 270                       if (word_ == 0)                                   \
 271                         break;                                          \
 272                     }                                                   \
 273                 }                                                       \
 274             }                                                           \
 275                                                                         \
 276           bit_num_ = 0;                                                 \
 277         }                                                               \
 278                                                                         \
 279       word_num_ = 0;                                                    \
 280     }                                                                   \
 281 } while (0)
 282
 283 /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
 284    BITNUM to the bit number and executing CODE for all bits that are set in
 285    the both bitmaps.  */
 286
 287 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE)   \
 288 do {                                                                    \
 289   bitmap_element *ptr1_ = (BITMAP1)->first;                             \
 290   bitmap_element *ptr2_ = (BITMAP2)->first;                             \
 291   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 292   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 293   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 294                         % BITMAP_ELEMENT_WORDS);                        \
 295                                                                         \
 296   /* Find the block the minimum bit is in in the first bitmap.  */      \
 297   while (ptr1_ != 0 && ptr1_->indx < indx_)                             \
 298     ptr1_ = ptr1_->next;                                                \
 299                                                                         \
 300   if (ptr1_ != 0 && ptr1_->indx != indx_)                               \
 301     {                                                                   \
 302       bit_num_ = 0;                                                     \
 303       word_num_ = 0;                                                    \
 304     }                                                                   \
 305                                                                         \
 306   for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)                              \
 307     {                                                                   \
 308       /* Advance BITMAP2 to the equivalent link */                      \
 309       while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)                   \
 310         ptr2_ = ptr2_->next;                                            \
 311                                                                         \
 312       if (ptr2_ == 0)                                                   \
 313         {                                                               \
 314           /* If there are no more elements in BITMAP2, exit loop now.*/ \
 315           ptr1_ = (bitmap_element *)0;                                  \
 316           break;                                                        \
 317         }                                                               \
 318       else if (ptr2_->indx > ptr1_->indx)                               \
 319         {                                                               \
 320           bit_num_ = word_num_ = 0;                                     \
 321           continue;                                                     \
 322         }                                                               \
 323                                                                         \
 324       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 325         {                                                               \
 326           unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]        \
 327                                           & ptr2_->bits[word_num_]);    \
 328           if (word_ != 0)                                               \
 329             {                                                           \
 330               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 331                 {                                                       \
 332                   unsigned HOST_WIDE_INT mask_                          \
 333                     = ((unsigned HOST_WIDE_INT)1) << bit_num_;          \
 334                                                                         \
 335                   if ((word_ & mask_) != 0)                             \
 336                     {                                                   \
 337                       word_ &= ~ mask_;                                 \
 338                       (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
 339                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 340                                   + bit_num_);                          \
 341                                                                         \
 342                       CODE;                                             \
 343                       if (word_ == 0)                                   \
 344                         break;                                          \
 345                     }                                                   \
 346                 }                                                       \
 347             }                                                           \
 348                                                                         \
 349           bit_num_ = 0;                                                 \
 350         }                                                               \
 351                                                                         \
 352       word_num_ = 0;                                                    \
 353     }                                                                   \
 354 } while (0)
 355
 356 #endif /* GCC_BITMAP_H */