gcc/bitmap.h

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