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 /* Number of words to use for each element in the linked list.  */
  22
  23 #ifndef BITMAP_ELEMENT_WORDS
  24 #define BITMAP_ELEMENT_WORDS 2
  25 #endif
  26
  27 /* Number of bits in each actual element of a bitmap.  We get slightly better
  28    code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if
  29    bits is unsigned, assuming it is a power of 2.  */
  30
  31 #define BITMAP_ELEMENT_ALL_BITS \
  32   ((unsigned) (BITMAP_ELEMENT_WORDS * HOST_BITS_PER_WIDE_INT))
  33
  34 /* Bitmap set element.  We use a linked list to hold only the bits that
  35    are set.  This allows for use to grow the bitset dynamically without
  36    having to realloc and copy a giant bit array.  The `prev' field is
  37    undefined for an element on the free list.  */
  38
  39 typedef struct bitmap_element_def
  40 {
  41   struct bitmap_element_def *next;              /* Next element. */
  42   struct bitmap_element_def *prev;              /* Previous element. */
  43   unsigned int indx;                    /* regno/BITMAP_ELEMENT_ALL_BITS. */
  44   unsigned HOST_WIDE_INT bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */
  45 } bitmap_element;
  46
  47 /* Head of bitmap linked list.  */
  48 typedef struct bitmap_head_def {
  49   bitmap_element *first;        /* First element in linked list. */
  50   bitmap_element *current;      /* Last element looked at. */
  51   unsigned int indx;            /* Index of last element looked at. */
  52 } bitmap_head, *bitmap;
  53
  54 /* Enumeration giving the various operations we support.  */
  55 enum bitmap_bits {
  56   BITMAP_AND,                   /* TO = FROM1 & FROM2 */
  57   BITMAP_AND_COMPL,             /* TO = FROM1 & ~ FROM2 */
  58   BITMAP_IOR,                   /* TO = FROM1 | FROM2 */
  59   BITMAP_XOR                    /* TO = FROM1 ^ FROM2 */
  60 };
  61
  62 /* Global data */
  63 extern bitmap_element *bitmap_free;     /* Freelist of bitmap elements */
  64 extern bitmap_element bitmap_zero;      /* Zero bitmap element */
  65
  66 /* Clear a bitmap by freeing up the linked list.  */
  67 extern void bitmap_clear PROTO((bitmap));
  68
  69 /* Copy a bitmap to another bitmap. */
  70 extern void bitmap_copy PROTO((bitmap, bitmap));
  71
  72 /* True if two bitmaps are identical.  */
  73 extern int bitmap_equal_p PROTO((bitmap, bitmap));
  74
  75 /* Perform an operation on two bitmaps, yielding a third.  */
  76 extern int bitmap_operation PROTO((bitmap, bitmap, bitmap, enum bitmap_bits));
  77
  78 /* `or' into one bitmap the `and' of a second bitmap witih the complement
  79    of a third.  */
  80 extern void bitmap_ior_and_compl PROTO((bitmap, bitmap, bitmap));
  81
  82 /* Clear a single register in a register set.  */
  83 extern void bitmap_clear_bit PROTO((bitmap, int));
  84
  85 /* Set a single register in a register set.  */
  86 extern void bitmap_set_bit PROTO((bitmap, int));
  87
  88 /* Return true if a register is set in a register set.  */
  89 extern int bitmap_bit_p PROTO((bitmap, int));
  90
  91 /* Debug functions to print a bitmap linked list.  */
  92 extern void debug_bitmap PROTO((bitmap));
  93 extern void debug_bitmap_file PROTO((FILE *, bitmap));
  94
  95 /* Print a bitmap */
  96 extern void bitmap_print PROTO((FILE *, bitmap, const char *, const char *));
  97
  98 /* Initialize a bitmap header.  */
  99 extern bitmap bitmap_initialize PROTO((bitmap));
 100
 101 /* Release all memory held by bitmaps.  */
 102 extern void bitmap_release_memory PROTO((void));
 103
 104 extern void debug_bitmap PROTO((bitmap));
 105
 106 /* Allocate a bitmap with oballoc.  */
 107 #define BITMAP_OBSTACK_ALLOC(OBSTACK)                           \
 108   bitmap_initialize ((bitmap) obstack_alloc (OBSTACK, sizeof (bitmap_head)))
 109
 110 /* Allocate a bitmap with alloca.  */
 111 #define BITMAP_ALLOCA()                                         \
 112   bitmap_initialize ((bitmap) alloca (sizeof (bitmap_head)))
 113
 114 /* Do any cleanup needed on a bitmap when it is no longer used.  */
 115 #define BITMAP_FREE(BITMAP)                                     \
 116 do {                            \
 117   if (BITMAP)                   \
 118     {                           \
 119       bitmap_clear (BITMAP);    \
 120       (BITMAP) = 0;             \
 121     }                                                                   \
 122 } while (0)
 123
 124 /* Do any one-time initializations needed for bitmaps.  */
 125 #define BITMAP_INIT_ONCE()
 126
 127 /* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the
 128    bit number and executing CODE for all bits that are set. */
 129
 130 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE)             \
 131 do {                                                                    \
 132   bitmap_element *ptr_ = (BITMAP)->first;                               \
 133   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 134   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 135   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 136                         % BITMAP_ELEMENT_WORDS);                        \
 137                                                                         \
 138                                                                         \
 139   /* Find the block the minimum bit is in.  */                          \
 140   while (ptr_ != 0 && ptr_->indx < indx_)                               \
 141     ptr_ = ptr_->next;                                                  \
 142                                                                         \
 143   if (ptr_ != 0 && ptr_->indx != indx_)                                 \
 144     {                                                                   \
 145       bit_num_ = 0;                                                     \
 146       word_num_ = 0;                                                    \
 147     }                                                                   \
 148                                                                         \
 149   for (; ptr_ != 0; ptr_ = ptr_->next)                                  \
 150     {                                                                   \
 151       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 152         {                                                               \
 153           unsigned HOST_WIDE_INT word_ = ptr_->bits[word_num_];         \
 154                                                                         \
 155           if (word_ != 0)                                               \
 156             {                                                           \
 157               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 158                 {                                                       \
 159                   unsigned HOST_WIDE_INT mask_                          \
 160                     = ((unsigned HOST_WIDE_INT) 1) << bit_num_;         \
 161                                                                         \
 162                   if ((word_ & mask_) != 0)                             \
 163                     {                                                   \
 164                       word_ &= ~ mask_;                                 \
 165                       (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS  \
 166                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 167                                   + bit_num_);                          \
 168                       CODE;                                             \
 169                                                                         \
 170                       if (word_ == 0)                                   \
 171                         break;                                          \
 172                     }                                                   \
 173                 }                                                       \
 174             }                                                           \
 175                                                                         \
 176           bit_num_ = 0;                                                 \
 177         }                                                               \
 178                                                                         \
 179       word_num_ = 0;                                                    \
 180     }                                                                   \
 181 } while (0)
 182
 183 /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
 184    BITNUM to the bit number and executing CODE for all bits that are set in
 185    the first bitmap and not set in the second. */
 186
 187 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \
 188 do {                                                                    \
 189   bitmap_element *ptr1_ = (BITMAP1)->first;                             \
 190   bitmap_element *ptr2_ = (BITMAP2)->first;                             \
 191   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 192   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 193   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 194                         % BITMAP_ELEMENT_WORDS);                        \
 195                                                                         \
 196   /* Find the block the minimum bit is in in the first bitmap.  */      \
 197   while (ptr1_ != 0 && ptr1_->indx < indx_)                             \
 198     ptr1_ = ptr1_->next;                                                \
 199                                                                         \
 200   if (ptr1_ != 0 && ptr1_->indx != indx_)                               \
 201     {                                                                   \
 202       bit_num_ = 0;                                                     \
 203       word_num_ = 0;                                                    \
 204     }                                                                   \
 205                                                                         \
 206   for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)                              \
 207     {                                                                   \
 208       /* Advance BITMAP2 to the equivalent link, using an all           \
 209          zero element if an equivalent link doesn't exist.  */          \
 210       bitmap_element *tmp2_;                                            \
 211                                                                         \
 212       while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)                   \
 213         ptr2_ = ptr2_->next;                                            \
 214                                                                         \
 215       tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx)               \
 216                ? ptr2_ : &bitmap_zero);                                 \
 217                                                                         \
 218       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 219         {                                                               \
 220           unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]        \
 221                                           & ~ tmp2_->bits[word_num_]);  \
 222           if (word_ != 0)                                               \
 223             {                                                           \
 224               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 225                 {                                                       \
 226                   unsigned HOST_WIDE_INT mask_                          \
 227                     = ((unsigned HOST_WIDE_INT)1) << bit_num_;          \
 228                                                                         \
 229                   if ((word_ & mask_) != 0)                             \
 230                     {                                                   \
 231                       word_ &= ~ mask_;                                 \
 232                       (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
 233                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 234                                   + bit_num_);                          \
 235                                                                         \
 236                       CODE;                                             \
 237                       if (word_ == 0)                                   \
 238                         break;                                          \
 239                     }                                                   \
 240                 }                                                       \
 241             }                                                           \
 242                                                                         \
 243           bit_num_ = 0;                                                 \
 244         }                                                               \
 245                                                                         \
 246       word_num_ = 0;                                                    \
 247     }                                                                   \
 248 } while (0)
 249
 250 /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
 251    BITNUM to the bit number and executing CODE for all bits that are set in
 252    the both bitmaps. */
 253
 254 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE)   \
 255 do {                                                                    \
 256   bitmap_element *ptr1_ = (BITMAP1)->first;                             \
 257   bitmap_element *ptr2_ = (BITMAP2)->first;                             \
 258   unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;                 \
 259   unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);      \
 260   unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))   \
 261                         % BITMAP_ELEMENT_WORDS);                        \
 262                                                                         \
 263   /* Find the block the minimum bit is in in the first bitmap.  */      \
 264   while (ptr1_ != 0 && ptr1_->indx < indx_)                             \
 265     ptr1_ = ptr1_->next;                                                \
 266                                                                         \
 267   if (ptr1_ != 0 && ptr1_->indx != indx_)                               \
 268     {                                                                   \
 269       bit_num_ = 0;                                                     \
 270       word_num_ = 0;                                                    \
 271     }                                                                   \
 272                                                                         \
 273   for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)                              \
 274     {                                                                   \
 275       /* Advance BITMAP2 to the equivalent link */                      \
 276       while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)                   \
 277         ptr2_ = ptr2_->next;                                            \
 278                                                                         \
 279       if (ptr2_ == 0)                                                   \
 280         {                                                               \
 281           /* If there are no more elements in BITMAP2, exit loop now.*/ \
 282           ptr1_ = (bitmap_element *)0;                                  \
 283           break;                                                        \
 284         }                                                               \
 285       else if (ptr2_->indx > ptr1_->indx)                               \
 286         {                                                               \
 287           bit_num_ = word_num_ = 0;                                     \
 288           continue;                                                     \
 289         }                                                               \
 290                                                                         \
 291       for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)             \
 292         {                                                               \
 293           unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]        \
 294                                           & ptr2_->bits[word_num_]);    \
 295           if (word_ != 0)                                               \
 296             {                                                           \
 297               for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)     \
 298                 {                                                       \
 299                   unsigned HOST_WIDE_INT mask_                          \
 300                     = ((unsigned HOST_WIDE_INT)1) << bit_num_;          \
 301                                                                         \
 302                   if ((word_ & mask_) != 0)                             \
 303                     {                                                   \
 304                       word_ &= ~ mask_;                                 \
 305                       (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
 306                                   + word_num_ * HOST_BITS_PER_WIDE_INT  \
 307                                   + bit_num_);                          \
 308                                                                         \
 309                       CODE;                                             \
 310                       if (word_ == 0)                                   \
 311                         break;                                          \
 312                     }                                                   \
 313                 }                                                       \
 314             }                                                           \
 315                                                                         \
 316           bit_num_ = 0;                                                 \
 317         }                                                               \
 318                                                                         \
 319       word_num_ = 0;                                                    \
 320     }                                                                   \
 321 } while (0)