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