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 one-time initializations needed for bitmaps.  */
 132 #define BITMAP_INIT_ONCE()
 133
 134 /* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the
 135    bit number and executing CODE for all bits that are set. */
 136
 137 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE)             \
 138 do {                                                                    \
 139   bitmap_element *ptr_ = (BITMAP)->first;                               \
 140   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 141   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 142   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 143                         % BITMAP_ELEMENT_WORDS);                        \
 144                                                                         \
 145                                                                         \
 146   /* Find the block the minimum bit is in.  */                          \
 147   while (ptr_ != 0 && ptr_->indx < indx_)                               \
 148     ptr_ = ptr_->next;                                                  \
 149                                                                         \
 150   if (ptr_ != 0 && ptr_->indx != indx_)                                 \
 151     {                                                                   \
 152       bit_num_ = 0;                                                     \
 153       word_num_ = 0;                                                    \
 154     }                                                                   \
 155                                                                         \
 156   for (; ptr_ != 0; ptr_ = ptr_->next)                                  \
 157     {                                                                   \
 158       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 159         {                                                               \
 160           unsigned HOST_WIDE_INT word_ = ptr_->bits[word_num_];         \
 161                                                                         \
 162           if (word_ != 0)                                               \
 163             {                                                           \
 164               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 165                 {                                                       \
 166                   unsigned HOST_WIDE_INT mask_                          \
 167                     = ((unsigned HOST_WIDE_INT) 1) << bit_num_;         \
 168                                                                         \
 169                   if ((word_ & mask_) != 0)                             \
 170                     {                                                   \
 171                       word_ &= ~ mask_;                                 \
 172                       (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS  \
 173                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 174                                   + bit_num_);                          \
 175                       CODE;                                             \
 176                                                                         \
 177                       if (word_ == 0)                                   \
 178                         break;                                          \
 179                     }                                                   \
 180                 }                                                       \
 181             }                                                           \
 182                                                                         \
 183           bit_num_ = 0;                                                 \
 184         }                                                               \
 185                                                                         \
 186       word_num_ = 0;                                                    \
 187     }                                                                   \
 188 } while (0)
 189
 190 /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
 191    BITNUM to the bit number and executing CODE for all bits that are set in
 192    the first bitmap and not set in the second. */
 193
 194 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \
 195 do {                                                                    \
 196   bitmap_element *ptr1_ = (BITMAP1)->first;                             \
 197   bitmap_element *ptr2_ = (BITMAP2)->first;                             \
 198   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 199   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 200   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 201                         % BITMAP_ELEMENT_WORDS);                        \
 202                                                                         \
 203   /* Find the block the minimum bit is in in the first bitmap.  */      \
 204   while (ptr1_ != 0 && ptr1_->indx < indx_)                             \
 205     ptr1_ = ptr1_->next;                                                \
 206                                                                         \
 207   if (ptr1_ != 0 && ptr1_->indx != indx_)                               \
 208     {                                                                   \
 209       bit_num_ = 0;                                                     \
 210       word_num_ = 0;                                                    \
 211     }                                                                   \
 212                                                                         \
 213   for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)                              \
 214     {                                                                   \
 215       /* Advance BITMAP2 to the equivalent link, using an all           \
 216          zero element if an equivalent link doesn't exist.  */          \
 217       bitmap_element *tmp2_;                                            \
 218                                                                         \
 219       while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)                   \
 220         ptr2_ = ptr2_->next;                                            \
 221                                                                         \
 222       tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx)               \
 223                ? ptr2_ : &bitmap_zero);                                 \
 224                                                                         \
 225       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 226         {                                                               \
 227           unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]        \
 228                                           & ~ tmp2_->bits[word_num_]);  \
 229           if (word_ != 0)                                               \
 230             {                                                           \
 231               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 232                 {                                                       \
 233                   unsigned HOST_WIDE_INT mask_                          \
 234                     = ((unsigned HOST_WIDE_INT)1) << bit_num_;          \
 235                                                                         \
 236                   if ((word_ & mask_) != 0)                             \
 237                     {                                                   \
 238                       word_ &= ~ mask_;                                 \
 239                       (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
 240                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 241                                   + bit_num_);                          \
 242                                                                         \
 243                       CODE;                                             \
 244                       if (word_ == 0)                                   \
 245                         break;                                          \
 246                     }                                                   \
 247                 }                                                       \
 248             }                                                           \
 249                                                                         \
 250           bit_num_ = 0;                                                 \
 251         }                                                               \
 252                                                                         \
 253       word_num_ = 0;                                                    \
 254     }                                                                   \
 255 } while (0)
 256
 257 /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
 258    BITNUM to the bit number and executing CODE for all bits that are set in
 259    the both bitmaps. */
 260
 261 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE)   \
 262 do {                                                                    \
 263   bitmap_element *ptr1_ = (BITMAP1)->first;                             \
 264   bitmap_element *ptr2_ = (BITMAP2)->first;                             \
 265   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 266   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 267   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 268                         % BITMAP_ELEMENT_WORDS);                        \
 269                                                                         \
 270   /* Find the block the minimum bit is in in the first bitmap.  */      \
 271   while (ptr1_ != 0 && ptr1_->indx < indx_)                             \
 272     ptr1_ = ptr1_->next;                                                \
 273                                                                         \
 274   if (ptr1_ != 0 && ptr1_->indx != indx_)                               \
 275     {                                                                   \
 276       bit_num_ = 0;                                                     \
 277       word_num_ = 0;                                                    \
 278     }                                                                   \
 279                                                                         \
 280   for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)                              \
 281     {                                                                   \
 282       /* Advance BITMAP2 to the equivalent link */                      \
 283       while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)                   \
 284         ptr2_ = ptr2_->next;                                            \
 285                                                                         \
 286       if (ptr2_ == 0)                                                   \
 287         {                                                               \
 288           /* If there are no more elements in BITMAP2, exit loop now.*/ \
 289           ptr1_ = (bitmap_element *)0;                                  \
 290           break;                                                        \
 291         }                                                               \
 292       else if (ptr2_->indx > ptr1_->indx)                               \
 293         {                                                               \
 294           bit_num_ = word_num_ = 0;                                     \
 295           continue;                                                     \
 296         }                                                               \
 297                                                                         \
 298       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 299         {                                                               \
 300           unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]        \
 301                                           & ptr2_->bits[word_num_]);    \
 302           if (word_ != 0)                                               \
 303             {                                                           \
 304               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 305                 {                                                       \
 306                   unsigned HOST_WIDE_INT mask_                          \
 307                     = ((unsigned HOST_WIDE_INT)1) << bit_num_;          \
 308                                                                         \
 309                   if ((word_ & mask_) != 0)                             \
 310                     {                                                   \
 311                       word_ &= ~ mask_;                                 \
 312                       (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
 313                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 314                                   + bit_num_);                          \
 315                                                                         \
 316                       CODE;                                             \
 317                       if (word_ == 0)                                   \
 318                         break;                                          \
 319                     }                                                   \
 320                 }                                                       \
 321             }                                                           \
 322                                                                         \
 323           bit_num_ = 0;                                                 \
 324         }                                                               \
 325                                                                         \
 326       word_num_ = 0;                                                    \
 327     }                                                                   \
 328 } while (0)
 329
 330 #endif /* _BITMAP_H */