gcc/bitmap.h

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
   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 /* Iterator for bitmaps.  */
 166
 167 typedef struct
 168 {
 169   /* Actual elements in the bitmaps.  */
 170   bitmap_element *ptr1, *ptr2;
 171
 172   /* Position of an actual word in the elements.  */
 173   unsigned word;
 174
 175   /* Position of a bit corresponding to the start of word.  */
 176   unsigned word_bit;
 177
 178   /* Position of the actual bit.  */
 179   unsigned bit;
 180
 181   /* Contents of the actually processed word.  When finding next bit
 182      it is shifted right, so that the actual bit is always the least
 183      significant bit of ACTUAL.  */
 184   BITMAP_WORD actual;
 185 } bitmap_iterator;
 186
 187 /* Moves the iterator BI to the first set bit on or after the current
 188    position in bitmap and returns the bit if available.  The bit is
 189    found in ACTUAL field only.  */
 190
 191 static inline unsigned
 192 bmp_iter_common_next_1 (bitmap_iterator *bi)
 193 {
 194   while (!(bi->actual & 1))
 195     {
 196       bi->actual >>= 1;
 197       bi->bit++;
 198     }
 199
 200   return bi->bit;
 201 }
 202
 203 /* Moves the iterator BI to the first set bit on or after the current
 204    position in bitmap and returns the bit if available.  */
 205
 206 static inline unsigned
 207 bmp_iter_single_next_1 (bitmap_iterator *bi)
 208 {
 209   if (bi->actual)
 210     return bmp_iter_common_next_1 (bi);
 211
 212   bi->word++;
 213   bi->word_bit += BITMAP_WORD_BITS;
 214
 215   while (1)
 216     {
 217       for (;
 218            bi->word < BITMAP_ELEMENT_WORDS;
 219            bi->word++, bi->word_bit += BITMAP_WORD_BITS)
 220         {
 221           bi->actual = bi->ptr1->bits[bi->word];
 222           if (bi->actual)
 223             {
 224               bi->bit = bi->word_bit;
 225               return bmp_iter_common_next_1 (bi);
 226             }
 227         }
 228
 229       bi->ptr1 = bi->ptr1->next;
 230       if (!bi->ptr1)
 231         return 0;
 232
 233       bi->word = 0;
 234       bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
 235     }
 236 }
 237
 238 /* Initializes a bitmap iterator BI for looping over bits of bitmap
 239    BMP, starting with bit MIN.  Returns the first bit of BMP greater
 240    or equal to MIN if there is any.  */
 241
 242 static inline unsigned
 243 bmp_iter_single_init (bitmap_iterator *bi, bitmap bmp, unsigned min)
 244 {
 245   unsigned indx = min / BITMAP_ELEMENT_ALL_BITS;
 246
 247   for (bi->ptr1 = bmp->first;
 248        bi->ptr1 && bi->ptr1->indx < indx;
 249        bi->ptr1 = bi->ptr1->next)
 250     continue;
 251
 252   if (!bi->ptr1)
 253     {
 254       /* To avoid warnings.  */
 255       bi->word = 0;
 256       bi->bit = 0;
 257       bi->word_bit = 0;
 258       bi->actual = 0;
 259       bi->ptr2 = NULL;
 260       return 0;
 261     }
 262
 263   if (bi->ptr1->indx == indx)
 264     {
 265       unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx;
 266       unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS;
 267       unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS;
 268
 269       bi->word = word_in_elt;
 270       bi->word_bit = min - bit_in_word;
 271       bi->bit = min;
 272       bi->actual = bi->ptr1->bits[word_in_elt] >> bit_in_word;
 273     }
 274   else
 275     {
 276       bi->word = 0;
 277       bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
 278       bi->word_bit = bi->bit;
 279       bi->actual = bi->ptr1->bits[0];
 280     }
 281
 282   return bmp_iter_single_next_1 (bi);
 283 }
 284
 285 /* Returns true if all elements of the bitmap referred to by iterator BI
 286    were processed.  */
 287
 288 static inline bool
 289 bmp_iter_end_p (bitmap_iterator bi)
 290 {
 291   return bi.ptr1 == NULL;
 292 }
 293
 294 /* Moves the iterator BI to the next bit of bitmap and returns the bit
 295    if available.  */
 296
 297 static inline unsigned
 298 bmp_iter_single_next (bitmap_iterator *bi)
 299 {
 300   bi->bit++;
 301   bi->actual >>= 1;
 302   return bmp_iter_single_next_1 (bi);
 303 }
 304
 305 /* Loop over all bits in BITMAP, starting with MIN and setting BITNUM to
 306    the bit number.  ITER is a bitmap iterator.  */
 307
 308 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)             \
 309   for ((BITNUM) = bmp_iter_single_init (&(ITER), (BITMAP), (MIN));      \
 310        !bmp_iter_end_p (ITER);                                  \
 311        (BITNUM) = bmp_iter_single_next (&(ITER)))
 312
 313 /* Moves the iterator BI to the first set bit on or after the current
 314    position in difference of bitmaps and returns the bit if available.  */
 315
 316 static inline unsigned
 317 bmp_iter_and_not_next_1 (bitmap_iterator *bi)
 318 {
 319   if (bi->actual)
 320     return bmp_iter_common_next_1 (bi);
 321
 322   bi->word++;
 323   bi->word_bit += BITMAP_WORD_BITS;
 324
 325   while (1)
 326     {
 327       bitmap_element *snd;
 328
 329       if (bi->ptr2 && bi->ptr2->indx == bi->ptr1->indx)
 330         snd = bi->ptr2;
 331       else
 332         snd = &bitmap_zero_bits;
 333
 334       for (;
 335            bi->word < BITMAP_ELEMENT_WORDS;
 336            bi->word++, bi->word_bit += BITMAP_WORD_BITS)
 337         {
 338           bi->actual = (bi->ptr1->bits[bi->word]
 339                         & ~snd->bits[bi->word]);
 340           if (bi->actual)
 341             {
 342               bi->bit = bi->word_bit;
 343               return bmp_iter_common_next_1 (bi);
 344             }
 345         }
 346
 347       bi->ptr1 = bi->ptr1->next;
 348       if (!bi->ptr1)
 349         return 0;
 350
 351       while (bi->ptr2
 352              && bi->ptr2->indx < bi->ptr1->indx)
 353         bi->ptr2 = bi->ptr2->next;
 354
 355       bi->word = 0;
 356       bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
 357     }
 358 }
 359
 360 /* Initializes a bitmap iterator BI for looping over bits of bitmap
 361    BMP1 &~ BMP2, starting with bit MIN.  Returns the first bit of
 362    BMP1 &~ BMP2 greater or equal to MIN if there is any.  */
 363
 364 static inline unsigned
 365 bmp_iter_and_not_init (bitmap_iterator *bi, bitmap bmp1, bitmap bmp2,
 366                        unsigned min)
 367 {
 368   unsigned indx = min / BITMAP_ELEMENT_ALL_BITS;
 369
 370   for (bi->ptr1 = bmp1->first;
 371        bi->ptr1 && bi->ptr1->indx < indx;
 372        bi->ptr1 = bi->ptr1->next)
 373     continue;
 374
 375   if (!bi->ptr1)
 376     {
 377       /* To avoid warnings.  */
 378       bi->word = 0;
 379       bi->bit = 0;
 380       bi->word_bit = 0;
 381       bi->actual = 0;
 382       bi->ptr2 = NULL;
 383       return 0;
 384     }
 385
 386   for (bi->ptr2 = bmp2->first;
 387        bi->ptr2 && bi->ptr2->indx < bi->ptr1->indx;
 388        bi->ptr2 = bi->ptr2->next)
 389     continue;
 390
 391   if (bi->ptr1->indx == indx)
 392     {
 393       unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx;
 394       unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS;
 395       unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS;
 396
 397       bi->word = word_in_elt;
 398       bi->word_bit = min - bit_in_word;
 399       bi->bit = min;
 400
 401       if (bi->ptr2 && bi->ptr2->indx == indx)
 402         bi->actual = (bi->ptr1->bits[word_in_elt]
 403                       & ~bi->ptr2->bits[word_in_elt]) >> bit_in_word;
 404       else
 405        bi->actual = bi->ptr1->bits[word_in_elt] >> bit_in_word;
 406     }
 407   else
 408     {
 409       bi->word = 0;
 410       bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
 411       bi->word_bit = bi->bit;
 412
 413       if (bi->ptr2 && bi->ptr2->indx == bi->ptr1->indx)
 414         bi->actual = (bi->ptr1->bits[0] & ~bi->ptr2->bits[0]);
 415       else
 416         bi->actual = bi->ptr1->bits[0];
 417     }
 418
 419   return bmp_iter_and_not_next_1 (bi);
 420 }
 421
 422 /* Moves the iterator BI to the next bit of difference of bitmaps and returns
 423    the bit if available.  */
 424
 425 static inline unsigned
 426 bmp_iter_and_not_next (bitmap_iterator *bi)
 427 {
 428   bi->bit++;
 429   bi->actual >>= 1;
 430   return bmp_iter_and_not_next_1 (bi);
 431 }
 432
 433 /* Loop over all bits in BMP1 and BMP2, starting with MIN, setting
 434    BITNUM to the bit number for all bits that are set in the first bitmap
 435    and not set in the second.  ITER is a bitmap iterator.  */
 436
 437 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BMP1, BMP2, MIN, BITNUM, ITER)   \
 438   for ((BITNUM) = bmp_iter_and_not_init (&(ITER), (BMP1), (BMP2), (MIN)); \
 439        !bmp_iter_end_p (ITER);                                          \
 440        (BITNUM) = bmp_iter_and_not_next (&(ITER)))
 441
 442 /* Moves the iterator BI to the first set bit on or after the current
 443    position in intersection of bitmaps and returns the bit if available.  */
 444
 445 static inline unsigned
 446 bmp_iter_and_next_1 (bitmap_iterator *bi)
 447 {
 448   if (bi->actual)
 449     return bmp_iter_common_next_1 (bi);
 450
 451   bi->word++;
 452   bi->word_bit += BITMAP_WORD_BITS;
 453
 454   while (1)
 455     {
 456       for (;
 457            bi->word < BITMAP_ELEMENT_WORDS;
 458            bi->word++, bi->word_bit += BITMAP_WORD_BITS)
 459         {
 460           bi->actual = (bi->ptr1->bits[bi->word]
 461                         & bi->ptr2->bits[bi->word]);
 462           if (bi->actual)
 463             {
 464               bi->bit = bi->word_bit;
 465               return bmp_iter_common_next_1 (bi);
 466             }
 467         }
 468
 469       do
 470         {
 471           bi->ptr1 = bi->ptr1->next;
 472           if (!bi->ptr1)
 473             return 0;
 474
 475           while (bi->ptr2->indx < bi->ptr1->indx)
 476             {
 477               bi->ptr2 = bi->ptr2->next;
 478               if (!bi->ptr2)
 479                 {
 480                   bi->ptr1 = NULL;
 481                   return 0;
 482                 }
 483             }
 484         }
 485       while (bi->ptr1->indx != bi->ptr2->indx);
 486
 487       bi->word = 0;
 488       bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
 489     }
 490 }
 491
 492 /* Initializes a bitmap iterator BI for looping over bits of bitmap
 493    BMP1 & BMP2, starting with bit MIN.  Returns the first bit of
 494    BMP1 & BMP2 greater or equal to MIN if there is any.  */
 495
 496 static inline unsigned
 497 bmp_iter_and_init (bitmap_iterator *bi, bitmap bmp1, bitmap bmp2,
 498                        unsigned min)
 499 {
 500   unsigned indx = min / BITMAP_ELEMENT_ALL_BITS;
 501
 502   for (bi->ptr1 = bmp1->first;
 503        bi->ptr1 && bi->ptr1->indx < indx;
 504        bi->ptr1 = bi->ptr1->next)
 505     continue;
 506
 507   if (!bi->ptr1)
 508     goto empty;
 509
 510   bi->ptr2 = bmp2->first;
 511   if (!bi->ptr2)
 512     goto empty;
 513
 514   while (1)
 515     {
 516       while (bi->ptr2->indx < bi->ptr1->indx)
 517         {
 518           bi->ptr2 = bi->ptr2->next;
 519           if (!bi->ptr2)
 520             goto empty;
 521         }
 522
 523       if (bi->ptr1->indx == bi->ptr2->indx)
 524         break;
 525
 526       bi->ptr1 = bi->ptr1->next;
 527       if (!bi->ptr1)
 528         goto empty;
 529     }
 530
 531   if (bi->ptr1->indx == indx)
 532     {
 533       unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx;
 534       unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS;
 535       unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS;
 536
 537       bi->word = word_in_elt;
 538       bi->word_bit = min - bit_in_word;
 539       bi->bit = min;
 540
 541       bi->actual = (bi->ptr1->bits[word_in_elt]
 542                     & bi->ptr2->bits[word_in_elt]) >> bit_in_word;
 543     }
 544   else
 545     {
 546       bi->word = 0;
 547       bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
 548       bi->word_bit = bi->bit;
 549
 550       bi->actual = (bi->ptr1->bits[0] & bi->ptr2->bits[0]);
 551     }
 552
 553   return bmp_iter_and_next_1 (bi);
 554
 555 empty:
 556   /* To avoid warnings.  */
 557   bi->word = 0;
 558   bi->bit = 0;
 559   bi->word_bit = 0;
 560   bi->actual = 0;
 561   bi->ptr1 = NULL;
 562   bi->ptr2 = NULL;
 563   return 0;
 564 }
 565
 566 /* Moves the iterator BI to the next bit of intersection of bitmaps and returns
 567    the bit if available.  */
 568
 569 static inline unsigned
 570 bmp_iter_and_next (bitmap_iterator *bi)
 571 {
 572   bi->bit++;
 573   bi->actual >>= 1;
 574   return bmp_iter_and_next_1 (bi);
 575 }
 576
 577 /* Loop over all bits in BMP1 and BMP2, starting with MIN, setting
 578    BITNUM to the bit number for all bits that are set in both bitmaps.
 579    ITER is a bitmap iterator.  */
 580
 581 #define EXECUTE_IF_AND_IN_BITMAP(BMP1, BMP2, MIN, BITNUM, ITER)         \
 582   for ((BITNUM) = bmp_iter_and_init (&(ITER), (BMP1), (BMP2), (MIN));   \
 583        !bmp_iter_end_p (ITER);                                          \
 584        (BITNUM) = bmp_iter_and_next (&(ITER)))
 585
 586 #endif /* GCC_BITMAP_H */