gcc/bitmap.h

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #ifndef _BITMAP_H
  22 #define _BITMAP_H 1
  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 } bitmap_head, *bitmap;
  56
  57 /* Enumeration giving the various operations we support.  */
  58 enum bitmap_bits {
  59   BITMAP_AND,                   /* TO = FROM1 & FROM2 */
  60   BITMAP_AND_COMPL,             /* TO = FROM1 & ~ FROM2 */
  61   BITMAP_IOR,                   /* TO = FROM1 | FROM2 */
  62   BITMAP_XOR                    /* TO = FROM1 ^ FROM2 */
  63 };
  64
  65 /* Global data */
  66 extern bitmap_element *bitmap_free;     /* Freelist of bitmap elements */
  67 extern bitmap_element bitmap_zero;      /* Zero bitmap element */
  68
  69 /* Clear a bitmap by freeing up the linked list.  */
  70 extern void bitmap_clear PROTO((bitmap));
  71
  72 /* Copy a bitmap to another bitmap. */
  73 extern void bitmap_copy PROTO((bitmap, bitmap));
  74
  75 /* True if two bitmaps are identical.  */
  76 extern int bitmap_equal_p PROTO((bitmap, bitmap));
  77
  78 /* Perform an operation on two bitmaps, yielding a third.  */
  79 extern int bitmap_operation PROTO((bitmap, bitmap, bitmap, enum bitmap_bits));
  80
  81 /* `or' into one bitmap the `and' of a second bitmap witih the complement
  82    of a third.  */
  83 extern void bitmap_ior_and_compl PROTO((bitmap, bitmap, bitmap));
  84
  85 /* Clear a single register in a register set.  */
  86 extern void bitmap_clear_bit PROTO((bitmap, int));
  87
  88 /* Set a single register in a register set.  */
  89 extern void bitmap_set_bit PROTO((bitmap, int));
  90
  91 /* Return true if a register is set in a register set.  */
  92 extern int bitmap_bit_p PROTO((bitmap, int));
  93
  94 /* Debug functions to print a bitmap linked list.  */
  95 extern void debug_bitmap PROTO((bitmap));
  96 extern void debug_bitmap_file PROTO((FILE *, bitmap));
  97
  98 /* Print a bitmap */
  99 extern void bitmap_print PROTO((FILE *, bitmap, const char *, const char *));
 100
 101 /* Initialize a bitmap header.  */
 102 extern bitmap bitmap_initialize PROTO((bitmap));
 103
 104 /* Release all memory held by bitmaps.  */
 105 extern void bitmap_release_memory PROTO((void));
 106
 107 extern void debug_bitmap PROTO((bitmap));
 108
 109 /* Allocate a bitmap with oballoc.  */
 110 #define BITMAP_OBSTACK_ALLOC(OBSTACK)                           \
 111   bitmap_initialize ((bitmap) obstack_alloc (OBSTACK, sizeof (bitmap_head)))
 112
 113 /* Allocate a bitmap with alloca.  */
 114 #define BITMAP_ALLOCA()                                         \
 115   bitmap_initialize ((bitmap) alloca (sizeof (bitmap_head)))
 116
 117 /* Allocate a bitmap with xmalloc.  */
 118 #define BITMAP_XMALLOC()                                        \
 119   bitmap_initialize ((bitmap) xmalloc (sizeof (bitmap_head)))
 120
 121 /* Do any cleanup needed on a bitmap when it is no longer used.  */
 122 #define BITMAP_FREE(BITMAP)                     \
 123 do {                                            \
 124   if (BITMAP)                                   \
 125     {                                           \
 126       bitmap_clear (BITMAP);                    \
 127       (BITMAP) = 0;                             \
 128     }                                           \
 129 } while (0)
 130
 131 /* Do any cleanup needed on an xmalloced bitmap when it is no longer used.  */
 132 #define BITMAP_XFREE(BITMAP)                    \
 133 do {                                            \
 134   if (BITMAP)                                   \
 135     {                                           \
 136       bitmap_clear (BITMAP);                    \
 137       free (BITMAP);                            \
 138       (BITMAP) = 0;                             \
 139     }                                           \
 140 } while (0)
 141
 142 /* Do any one-time initializations needed for bitmaps.  */
 143 #define BITMAP_INIT_ONCE()
 144
 145 /* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the
 146    bit number and executing CODE for all bits that are set. */
 147
 148 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE)             \
 149 do {                                                                    \
 150   bitmap_element *ptr_ = (BITMAP)->first;                               \
 151   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 152   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 153   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 154                         % BITMAP_ELEMENT_WORDS);                        \
 155                                                                         \
 156                                                                         \
 157   /* Find the block the minimum bit is in.  */                          \
 158   while (ptr_ != 0 && ptr_->indx < indx_)                               \
 159     ptr_ = ptr_->next;                                                  \
 160                                                                         \
 161   if (ptr_ != 0 && ptr_->indx != indx_)                                 \
 162     {                                                                   \
 163       bit_num_ = 0;                                                     \
 164       word_num_ = 0;                                                    \
 165     }                                                                   \
 166                                                                         \
 167   for (; ptr_ != 0; ptr_ = ptr_->next)                                  \
 168     {                                                                   \
 169       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 170         {                                                               \
 171           unsigned HOST_WIDE_INT word_ = ptr_->bits[word_num_];         \
 172                                                                         \
 173           if (word_ != 0)                                               \
 174             {                                                           \
 175               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 176                 {                                                       \
 177                   unsigned HOST_WIDE_INT mask_                          \
 178                     = ((unsigned HOST_WIDE_INT) 1) << bit_num_;         \
 179                                                                         \
 180                   if ((word_ & mask_) != 0)                             \
 181                     {                                                   \
 182                       word_ &= ~ mask_;                                 \
 183                       (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS  \
 184                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 185                                   + bit_num_);                          \
 186                       CODE;                                             \
 187                                                                         \
 188                       if (word_ == 0)                                   \
 189                         break;                                          \
 190                     }                                                   \
 191                 }                                                       \
 192             }                                                           \
 193                                                                         \
 194           bit_num_ = 0;                                                 \
 195         }                                                               \
 196                                                                         \
 197       word_num_ = 0;                                                    \
 198     }                                                                   \
 199 } while (0)
 200
 201 /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
 202    BITNUM to the bit number and executing CODE for all bits that are set in
 203    the first bitmap and not set in the second. */
 204
 205 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \
 206 do {                                                                    \
 207   bitmap_element *ptr1_ = (BITMAP1)->first;                             \
 208   bitmap_element *ptr2_ = (BITMAP2)->first;                             \
 209   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 210   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 211   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 212                         % BITMAP_ELEMENT_WORDS);                        \
 213                                                                         \
 214   /* Find the block the minimum bit is in in the first bitmap.  */      \
 215   while (ptr1_ != 0 && ptr1_->indx < indx_)                             \
 216     ptr1_ = ptr1_->next;                                                \
 217                                                                         \
 218   if (ptr1_ != 0 && ptr1_->indx != indx_)                               \
 219     {                                                                   \
 220       bit_num_ = 0;                                                     \
 221       word_num_ = 0;                                                    \
 222     }                                                                   \
 223                                                                         \
 224   for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)                              \
 225     {                                                                   \
 226       /* Advance BITMAP2 to the equivalent link, using an all           \
 227          zero element if an equivalent link doesn't exist.  */          \
 228       bitmap_element *tmp2_;                                            \
 229                                                                         \
 230       while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)                   \
 231         ptr2_ = ptr2_->next;                                            \
 232                                                                         \
 233       tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx)               \
 234                ? ptr2_ : &bitmap_zero);                                 \
 235                                                                         \
 236       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 237         {                                                               \
 238           unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]        \
 239                                           & ~ tmp2_->bits[word_num_]);  \
 240           if (word_ != 0)                                               \
 241             {                                                           \
 242               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 243                 {                                                       \
 244                   unsigned HOST_WIDE_INT mask_                          \
 245                     = ((unsigned HOST_WIDE_INT)1) << bit_num_;          \
 246                                                                         \
 247                   if ((word_ & mask_) != 0)                             \
 248                     {                                                   \
 249                       word_ &= ~ mask_;                                 \
 250                       (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
 251                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 252                                   + bit_num_);                          \
 253                                                                         \
 254                       CODE;                                             \
 255                       if (word_ == 0)                                   \
 256                         break;                                          \
 257                     }                                                   \
 258                 }                                                       \
 259             }                                                           \
 260                                                                         \
 261           bit_num_ = 0;                                                 \
 262         }                                                               \
 263                                                                         \
 264       word_num_ = 0;                                                    \
 265     }                                                                   \
 266 } while (0)
 267
 268 /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
 269    BITNUM to the bit number and executing CODE for all bits that are set in
 270    the both bitmaps. */
 271
 272 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE)   \
 273 do {                                                                    \
 274   bitmap_element *ptr1_ = (BITMAP1)->first;                             \
 275   bitmap_element *ptr2_ = (BITMAP2)->first;                             \
 276   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 277   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 278   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 279                         % BITMAP_ELEMENT_WORDS);                        \
 280                                                                         \
 281   /* Find the block the minimum bit is in in the first bitmap.  */      \
 282   while (ptr1_ != 0 && ptr1_->indx < indx_)                             \
 283     ptr1_ = ptr1_->next;                                                \
 284                                                                         \
 285   if (ptr1_ != 0 && ptr1_->indx != indx_)                               \
 286     {                                                                   \
 287       bit_num_ = 0;                                                     \
 288       word_num_ = 0;                                                    \
 289     }                                                                   \
 290                                                                         \
 291   for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)                              \
 292     {                                                                   \
 293       /* Advance BITMAP2 to the equivalent link */                      \
 294       while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)                   \
 295         ptr2_ = ptr2_->next;                                            \
 296                                                                         \
 297       if (ptr2_ == 0)                                                   \
 298         {                                                               \
 299           /* If there are no more elements in BITMAP2, exit loop now.*/ \
 300           ptr1_ = (bitmap_element *)0;                                  \
 301           break;                                                        \
 302         }                                                               \
 303       else if (ptr2_->indx > ptr1_->indx)                               \
 304         {                                                               \
 305           bit_num_ = word_num_ = 0;                                     \
 306           continue;                                                     \
 307         }                                                               \
 308                                                                         \
 309       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 310         {                                                               \
 311           unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]        \
 312                                           & ptr2_->bits[word_num_]);    \
 313           if (word_ != 0)                                               \
 314             {                                                           \
 315               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 316                 {                                                       \
 317                   unsigned HOST_WIDE_INT mask_                          \
 318                     = ((unsigned HOST_WIDE_INT)1) << bit_num_;          \
 319                                                                         \
 320                   if ((word_ & mask_) != 0)                             \
 321                     {                                                   \
 322                       word_ &= ~ mask_;                                 \
 323                       (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
 324                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 325                                   + bit_num_);                          \
 326                                                                         \
 327                       CODE;                                             \
 328                       if (word_ == 0)                                   \
 329                         break;                                          \
 330                     }                                                   \
 331                 }                                                       \
 332             }                                                           \
 333                                                                         \
 334           bit_num_ = 0;                                                 \
 335         }                                                               \
 336                                                                         \
 337       word_num_ = 0;                                                    \
 338     }                                                                   \
 339 } while (0)
 340
 341 #endif /* _BITMAP_H */