gcc/bitmap.h

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999, 2000 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 PARAMS ((bitmap));
  71
  72 /* Copy a bitmap to another bitmap. */
  73 extern void bitmap_copy PARAMS ((bitmap, bitmap));
  74
  75 /* True if two bitmaps are identical.  */
  76 extern int bitmap_equal_p PARAMS ((bitmap, bitmap));
  77
  78 /* Perform an operation on two bitmaps, yielding a third.  */
  79 extern int bitmap_operation PARAMS ((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 PARAMS ((bitmap, bitmap, bitmap));
  84
  85 /* Clear a single register in a register set.  */
  86 extern void bitmap_clear_bit PARAMS ((bitmap, int));
  87
  88 /* Set a single register in a register set.  */
  89 extern void bitmap_set_bit PARAMS ((bitmap, int));
  90
  91 /* Return true if a register is set in a register set.  */
  92 extern int bitmap_bit_p PARAMS ((bitmap, int));
  93
  94 /* Debug functions to print a bitmap linked list.  */
  95 extern void debug_bitmap PARAMS ((bitmap));
  96 extern void debug_bitmap_file PARAMS ((FILE *, bitmap));
  97
  98 /* Print a bitmap */
  99 extern void bitmap_print PARAMS ((FILE *, bitmap, const char *, const char *));
 100
 101 /* Initialize a bitmap header.  */
 102 extern bitmap bitmap_initialize PARAMS ((bitmap));
 103
 104 /* Release all memory held by bitmaps.  */
 105 extern void bitmap_release_memory PARAMS ((void));
 106
 107 /* Allocate a bitmap with oballoc.  */
 108 #define BITMAP_OBSTACK_ALLOC(OBSTACK)                           \
 109   bitmap_initialize ((bitmap) obstack_alloc (OBSTACK, sizeof (bitmap_head)))
 110
 111 /* Allocate a bitmap with alloca.  */
 112 #define BITMAP_ALLOCA()                                         \
 113   bitmap_initialize ((bitmap) alloca (sizeof (bitmap_head)))
 114
 115 /* Allocate a bitmap with xmalloc.  */
 116 #define BITMAP_XMALLOC()                                        \
 117   bitmap_initialize ((bitmap) xmalloc (sizeof (bitmap_head)))
 118
 119 /* Do any cleanup needed on a bitmap when it is no longer used.  */
 120 #define BITMAP_FREE(BITMAP)                     \
 121 do {                                            \
 122   if (BITMAP)                                   \
 123     {                                           \
 124       bitmap_clear (BITMAP);                    \
 125       (BITMAP) = 0;                             \
 126     }                                           \
 127 } while (0)
 128
 129 /* Do any cleanup needed on an xmalloced bitmap when it is no longer used.  */
 130 #define BITMAP_XFREE(BITMAP)                    \
 131 do {                                            \
 132   if (BITMAP)                                   \
 133     {                                           \
 134       bitmap_clear (BITMAP);                    \
 135       free (BITMAP);                            \
 136       (BITMAP) = 0;                             \
 137     }                                           \
 138 } while (0)
 139
 140 /* Do any one-time initializations needed for bitmaps.  */
 141 #define BITMAP_INIT_ONCE()
 142
 143 /* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the
 144    bit number and executing CODE for all bits that are set. */
 145
 146 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE)             \
 147 do {                                                                    \
 148   bitmap_element *ptr_ = (BITMAP)->first;                               \
 149   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 150   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 151   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 152                         % BITMAP_ELEMENT_WORDS);                        \
 153                                                                         \
 154                                                                         \
 155   /* Find the block the minimum bit is in.  */                          \
 156   while (ptr_ != 0 && ptr_->indx < indx_)                               \
 157     ptr_ = ptr_->next;                                                  \
 158                                                                         \
 159   if (ptr_ != 0 && ptr_->indx != indx_)                                 \
 160     {                                                                   \
 161       bit_num_ = 0;                                                     \
 162       word_num_ = 0;                                                    \
 163     }                                                                   \
 164                                                                         \
 165   for (; ptr_ != 0; ptr_ = ptr_->next)                                  \
 166     {                                                                   \
 167       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 168         {                                                               \
 169           unsigned HOST_WIDE_INT word_ = ptr_->bits[word_num_];         \
 170                                                                         \
 171           if (word_ != 0)                                               \
 172             {                                                           \
 173               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 174                 {                                                       \
 175                   unsigned HOST_WIDE_INT mask_                          \
 176                     = ((unsigned HOST_WIDE_INT) 1) << bit_num_;         \
 177                                                                         \
 178                   if ((word_ & mask_) != 0)                             \
 179                     {                                                   \
 180                       word_ &= ~ mask_;                                 \
 181                       (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS  \
 182                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 183                                   + bit_num_);                          \
 184                       CODE;                                             \
 185                                                                         \
 186                       if (word_ == 0)                                   \
 187                         break;                                          \
 188                     }                                                   \
 189                 }                                                       \
 190             }                                                           \
 191                                                                         \
 192           bit_num_ = 0;                                                 \
 193         }                                                               \
 194                                                                         \
 195       word_num_ = 0;                                                    \
 196     }                                                                   \
 197 } while (0)
 198
 199 /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
 200    BITNUM to the bit number and executing CODE for all bits that are set in
 201    the first bitmap and not set in the second. */
 202
 203 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \
 204 do {                                                                    \
 205   bitmap_element *ptr1_ = (BITMAP1)->first;                             \
 206   bitmap_element *ptr2_ = (BITMAP2)->first;                             \
 207   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 208   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 209   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 210                         % BITMAP_ELEMENT_WORDS);                        \
 211                                                                         \
 212   /* Find the block the minimum bit is in in the first bitmap.  */      \
 213   while (ptr1_ != 0 && ptr1_->indx < indx_)                             \
 214     ptr1_ = ptr1_->next;                                                \
 215                                                                         \
 216   if (ptr1_ != 0 && ptr1_->indx != indx_)                               \
 217     {                                                                   \
 218       bit_num_ = 0;                                                     \
 219       word_num_ = 0;                                                    \
 220     }                                                                   \
 221                                                                         \
 222   for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)                              \
 223     {                                                                   \
 224       /* Advance BITMAP2 to the equivalent link, using an all           \
 225          zero element if an equivalent link doesn't exist.  */          \
 226       bitmap_element *tmp2_;                                            \
 227                                                                         \
 228       while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)                   \
 229         ptr2_ = ptr2_->next;                                            \
 230                                                                         \
 231       tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx)               \
 232                ? ptr2_ : &bitmap_zero);                                 \
 233                                                                         \
 234       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 235         {                                                               \
 236           unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]        \
 237                                           & ~ tmp2_->bits[word_num_]);  \
 238           if (word_ != 0)                                               \
 239             {                                                           \
 240               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 241                 {                                                       \
 242                   unsigned HOST_WIDE_INT mask_                          \
 243                     = ((unsigned HOST_WIDE_INT)1) << bit_num_;          \
 244                                                                         \
 245                   if ((word_ & mask_) != 0)                             \
 246                     {                                                   \
 247                       word_ &= ~ mask_;                                 \
 248                       (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
 249                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 250                                   + bit_num_);                          \
 251                                                                         \
 252                       CODE;                                             \
 253                       if (word_ == 0)                                   \
 254                         break;                                          \
 255                     }                                                   \
 256                 }                                                       \
 257             }                                                           \
 258                                                                         \
 259           bit_num_ = 0;                                                 \
 260         }                                                               \
 261                                                                         \
 262       word_num_ = 0;                                                    \
 263     }                                                                   \
 264 } while (0)
 265
 266 /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
 267    BITNUM to the bit number and executing CODE for all bits that are set in
 268    the both bitmaps. */
 269
 270 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE)   \
 271 do {                                                                    \
 272   bitmap_element *ptr1_ = (BITMAP1)->first;                             \
 273   bitmap_element *ptr2_ = (BITMAP2)->first;                             \
 274   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 275   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 276   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 277                         % BITMAP_ELEMENT_WORDS);                        \
 278                                                                         \
 279   /* Find the block the minimum bit is in in the first bitmap.  */      \
 280   while (ptr1_ != 0 && ptr1_->indx < indx_)                             \
 281     ptr1_ = ptr1_->next;                                                \
 282                                                                         \
 283   if (ptr1_ != 0 && ptr1_->indx != indx_)                               \
 284     {                                                                   \
 285       bit_num_ = 0;                                                     \
 286       word_num_ = 0;                                                    \
 287     }                                                                   \
 288                                                                         \
 289   for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)                              \
 290     {                                                                   \
 291       /* Advance BITMAP2 to the equivalent link */                      \
 292       while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)                   \
 293         ptr2_ = ptr2_->next;                                            \
 294                                                                         \
 295       if (ptr2_ == 0)                                                   \
 296         {                                                               \
 297           /* If there are no more elements in BITMAP2, exit loop now.*/ \
 298           ptr1_ = (bitmap_element *)0;                                  \
 299           break;                                                        \
 300         }                                                               \
 301       else if (ptr2_->indx > ptr1_->indx)                               \
 302         {                                                               \
 303           bit_num_ = word_num_ = 0;                                     \
 304           continue;                                                     \
 305         }                                                               \
 306                                                                         \
 307       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 308         {                                                               \
 309           unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]        \
 310                                           & ptr2_->bits[word_num_]);    \
 311           if (word_ != 0)                                               \
 312             {                                                           \
 313               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 314                 {                                                       \
 315                   unsigned HOST_WIDE_INT mask_                          \
 316                     = ((unsigned HOST_WIDE_INT)1) << bit_num_;          \
 317                                                                         \
 318                   if ((word_ & mask_) != 0)                             \
 319                     {                                                   \
 320                       word_ &= ~ mask_;                                 \
 321                       (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
 322                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 323                                   + bit_num_);                          \
 324                                                                         \
 325                       CODE;                                             \
 326                       if (word_ == 0)                                   \
 327                         break;                                          \
 328                     }                                                   \
 329                 }                                                       \
 330             }                                                           \
 331                                                                         \
 332           bit_num_ = 0;                                                 \
 333         }                                                               \
 334                                                                         \
 335       word_num_ = 0;                                                    \
 336     }                                                                   \
 337 } while (0)
 338
 339 #endif /* _BITMAP_H */