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 long BITMAP_WORD;
  28 /* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
  29    it is used in preprocessor directives -- hence the 1u.  */
  30 #define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
  31
  32 /* Number of words to use for each element in the linked list.  */
  33
  34 #ifndef BITMAP_ELEMENT_WORDS
  35 #define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
  36 #endif
  37
  38 /* Number of bits in each actual element of a bitmap.  */
  39
  40 #define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
  41
  42 /* Obstack for allocating bitmaps and elements from.  */
  43 typedef struct bitmap_obstack GTY (())
  44 {
  45   struct bitmap_element_def *elements;
  46   struct bitmap_head_def *heads;
  47   struct obstack GTY ((skip)) obstack;
  48 } bitmap_obstack;
  49
  50 /* Bitmap set element.  We use a linked list to hold only the bits that
  51    are set.  This allows for use to grow the bitset dynamically without
  52    having to realloc and copy a giant bit array.  The `prev' field is
  53    undefined for an element on the free list.  */
  54
  55 typedef struct bitmap_element_def GTY(())
  56 {
  57   struct bitmap_element_def *next;              /* Next element.  */
  58   struct bitmap_element_def *prev;              /* Previous element.  */
  59   unsigned int indx;                    /* regno/BITMAP_ELEMENT_ALL_BITS.  */
  60   BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set.  */
  61 } bitmap_element;
  62
  63 /* Head of bitmap linked list.  */
  64 typedef struct bitmap_head_def GTY(()) {
  65   bitmap_element *first;        /* First element in linked list.  */
  66   bitmap_element *current;      /* Last element looked at.  */
  67   unsigned int indx;            /* Index of last element looked at.  */
  68   bitmap_obstack *obstack;      /* Obstack to allocate elements from.
  69                                    If NULL, then use ggc_alloc.  */
  70 } bitmap_head;
  71
  72
  73 typedef struct bitmap_head_def *bitmap;
  74
  75 /* Global data */
  76 extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
  77 extern bitmap_obstack bitmap_default_obstack;   /* Default bitmap obstack */
  78
  79 /* Clear a bitmap by freeing up the linked list.  */
  80 extern void bitmap_clear (bitmap);
  81
  82 /* Copy a bitmap to another bitmap.  */
  83 extern void bitmap_copy (bitmap, bitmap);
  84
  85 /* True if two bitmaps are identical.  */
  86 extern bool bitmap_equal_p (bitmap, bitmap);
  87
  88 /* True if the bitmaps intersect (their AND is non-empty).  */
  89 extern bool bitmap_intersect_p (bitmap, bitmap);
  90
  91 /* True if the complement of the second intersects the first (their
  92    AND_COMPL is non-empty).  */
  93 extern bool bitmap_intersect_compl_p (bitmap, bitmap);
  94
  95 /* True if MAP is an empty bitmap.  */
  96 #define bitmap_empty_p(MAP) (!(MAP)->first)
  97
  98 /* Boolean operations on bitmaps.  The _into variants are two operand
  99    versions that modify the first source operand.  The other variants
 100    are three operand versions that to not destroy the source bitmaps.
 101    The operations supported are &, & ~, |, ^.  */
 102 extern void bitmap_and (bitmap, bitmap, bitmap);
 103 extern void bitmap_and_into (bitmap, bitmap);
 104 extern void bitmap_and_compl (bitmap, bitmap, bitmap);
 105 extern void bitmap_and_compl_into (bitmap, bitmap);
 106 extern bool bitmap_ior (bitmap, bitmap, bitmap);
 107 extern bool bitmap_ior_into (bitmap, bitmap);
 108 extern void bitmap_xor (bitmap, bitmap, bitmap);
 109 extern void bitmap_xor_into (bitmap, bitmap);
 110
 111 /* DST = A | (B & ~C).  Return true if DST changes.  */
 112 extern bool bitmap_ior_and_compl (bitmap DST, bitmap A, bitmap B, bitmap C);
 113 /* A |= (B & ~C).  Return true if A changes.  */
 114 extern bool bitmap_ior_and_compl_into (bitmap DST, bitmap B, bitmap C);
 115
 116 /* Clear a single register in a register set.  */
 117 extern void bitmap_clear_bit (bitmap, int);
 118
 119 /* Set a single register in a register set.  */
 120 extern void bitmap_set_bit (bitmap, int);
 121
 122 /* Return true if a register is set in a register set.  */
 123 extern int bitmap_bit_p (bitmap, int);
 124
 125 /* Debug functions to print a bitmap linked list.  */
 126 extern void debug_bitmap (bitmap);
 127 extern void debug_bitmap_file (FILE *, bitmap);
 128
 129 /* Print a bitmap.  */
 130 extern void bitmap_print (FILE *, bitmap, const char *, const char *);
 131
 132 /* Initialize and releas a bitmap obstack.  */
 133 extern void bitmap_obstack_initialize (bitmap_obstack *);
 134 extern void bitmap_obstack_release (bitmap_obstack *);
 135
 136 /* Initialize a bitmap header.  OBSTACK indicates the bitmap obstack
 137    to allocate from, NULL for GC'd bitmap.  */
 138
 139 static inline void
 140 bitmap_initialize (bitmap head, bitmap_obstack *obstack)
 141 {
 142   head->first = head->current = NULL;
 143   head->obstack = obstack;
 144 }
 145
 146 /* Allocate and free bitmaps from obstack, malloc and gc'd memory.  */
 147 extern bitmap bitmap_obstack_alloc (bitmap_obstack *obstack);
 148 extern bitmap bitmap_gc_alloc (void);
 149 extern void bitmap_obstack_free (bitmap);
 150
 151 /* A few compatibility/functions macros for compatibility with sbitmaps */
 152 #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
 153 #define bitmap_zero(a) bitmap_clear (a)
 154 extern unsigned bitmap_first_set_bit (bitmap);
 155
 156 /* Allocate a bitmap from a bit obstack.  */
 157 #define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK)
 158
 159 /* Allocate a gc'd bitmap.  */
 160 #define BITMAP_GGC_ALLOC() bitmap_gc_alloc ()
 161
 162 /* Allocate a bitmap with xmalloc.  */
 163 #define BITMAP_XMALLOC() BITMAP_ALLOC (NULL)
 164
 165 /* Do any cleanup needed on a bitmap when it is no longer used.  */
 166 #define BITMAP_FREE(BITMAP)                     \
 167         ((void)(bitmap_obstack_free (BITMAP), (BITMAP) = NULL))
 168
 169 /* Do any cleanup needed on an xmalloced bitmap when it is no longer used.  */
 170 #define BITMAP_XFREE(BITMAP) BITMAP_FREE (BITMAP)
 171
 172 /* Iterator for bitmaps.  */
 173
 174 typedef struct
 175 {
 176   /* Pointer to the current bitmap element.  */
 177   bitmap_element *elt1;
 178
 179   /* Pointer to 2nd bitmap element when two are involved.  */
 180   bitmap_element *elt2;
 181
 182   /* Word within the current element.  */
 183   unsigned word_no;
 184
 185   /* Contents of the actually processed word.  When finding next bit
 186      it is shifted right, so that the actual bit is always the least
 187      significant bit of ACTUAL.  */
 188   BITMAP_WORD bits;
 189 } bitmap_iterator;
 190
 191 /* Initialize a single bitmap iterator.  START_BIT is the first bit to
 192    iterate from.  */
 193
 194 static inline void
 195 bmp_iter_set_init (bitmap_iterator *bi, bitmap map,
 196                    unsigned start_bit, unsigned *bit_no)
 197 {
 198   bi->elt1 = map->first;
 199   bi->elt2 = NULL;
 200
 201   /* Advance elt1 until it is not before the block containing start_bit.  */
 202   while (1)
 203     {
 204       if (!bi->elt1)
 205         {
 206           bi->elt1 = &bitmap_zero_bits;
 207           break;
 208         }
 209
 210       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
 211         break;
 212       bi->elt1 = bi->elt1->next;
 213     }
 214
 215   /* We might have gone past the start bit, so reinitialize it.  */
 216   if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
 217     start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 218
 219   /* Initialize for what is now start_bit.  */
 220   bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 221   bi->bits = bi->elt1->bits[bi->word_no];
 222   bi->bits >>= start_bit % BITMAP_WORD_BITS;
 223
 224   /* If this word is zero, we must make sure we're not pointing at the
 225      first bit, otherwise our incrementing to the next word boundary
 226      will fail.  It won't matter if this increment moves us into the
 227      next word.  */
 228   start_bit += !bi->bits;
 229
 230   *bit_no = start_bit;
 231 }
 232
 233 /* Initialize an iterator to iterate over the intersection of two
 234    bitmaps.  START_BIT is the bit to commence from.  */
 235
 236 static inline void
 237 bmp_iter_and_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
 238                    unsigned start_bit, unsigned *bit_no)
 239 {
 240   bi->elt1 = map1->first;
 241   bi->elt2 = map2->first;
 242
 243   /* Advance elt1 until it is not before the block containing
 244      start_bit.  */
 245   while (1)
 246     {
 247       if (!bi->elt1)
 248         {
 249           bi->elt2 = NULL;
 250           break;
 251         }
 252
 253       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
 254         break;
 255       bi->elt1 = bi->elt1->next;
 256     }
 257
 258   /* Advance elt2 until it is not before elt1.  */
 259   while (1)
 260     {
 261       if (!bi->elt2)
 262         {
 263           bi->elt1 = bi->elt2 = &bitmap_zero_bits;
 264           break;
 265         }
 266
 267       if (bi->elt2->indx >= bi->elt1->indx)
 268         break;
 269       bi->elt2 = bi->elt2->next;
 270     }
 271
 272   /* If we're at the same index, then we have some intersecting bits.  */
 273   if (bi->elt1->indx == bi->elt2->indx)
 274     {
 275       /* We might have advanced beyond the start_bit, so reinitialize
 276          for that.  */
 277       if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
 278         start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 279
 280       bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 281       bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
 282       bi->bits >>= start_bit % BITMAP_WORD_BITS;
 283     }
 284   else
 285     {
 286       /* Otherwise we must immediately advance elt1, so initialize for
 287          that.  */
 288       bi->word_no = BITMAP_ELEMENT_WORDS - 1;
 289       bi->bits = 0;
 290     }
 291
 292   /* If this word is zero, we must make sure we're not pointing at the
 293      first bit, otherwise our incrementing to the next word boundary
 294      will fail.  It won't matter if this increment moves us into the
 295      next word.  */
 296   start_bit += !bi->bits;
 297
 298   *bit_no = start_bit;
 299 }
 300
 301 /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2.
 302    */
 303
 304 static inline void
 305 bmp_iter_and_compl_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
 306                          unsigned start_bit, unsigned *bit_no)
 307 {
 308   bi->elt1 = map1->first;
 309   bi->elt2 = map2->first;
 310
 311   /* Advance elt1 until it is not before the block containing start_bit.  */
 312   while (1)
 313     {
 314       if (!bi->elt1)
 315         {
 316           bi->elt1 = &bitmap_zero_bits;
 317           break;
 318         }
 319
 320       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
 321         break;
 322       bi->elt1 = bi->elt1->next;
 323     }
 324
 325   /* Advance elt2 until it is not before elt1.  */
 326   while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
 327     bi->elt2 = bi->elt2->next;
 328
 329   /* We might have advanced beyond the start_bit, so reinitialize for
 330      that.  */
 331   if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
 332     start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 333
 334   bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 335   bi->bits = bi->elt1->bits[bi->word_no];
 336   if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
 337     bi->bits &= ~bi->elt2->bits[bi->word_no];
 338   bi->bits >>= start_bit % BITMAP_WORD_BITS;
 339
 340   /* If this word is zero, we must make sure we're not pointing at the
 341      first bit, otherwise our incrementing to the next word boundary
 342      will fail.  It won't matter if this increment moves us into the
 343      next word.  */
 344   start_bit += !bi->bits;
 345
 346   *bit_no = start_bit;
 347 }
 348
 349 /* Advance to the next bit in BI.  We don't advance to the next
 350    nonzero bit yet.  */
 351
 352 static inline void
 353 bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
 354 {
 355   bi->bits >>= 1;
 356   *bit_no += 1;
 357 }
 358
 359 /* Advance to the next nonzero bit of a single bitmap, we will have
 360    already advanced past the just iterated bit.  Return true if there
 361    is a bit to iterate.  */
 362
 363 static inline bool
 364 bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
 365 {
 366   /* If our current word is nonzero, it contains the bit we want.  */
 367   if (bi->bits)
 368     {
 369     next_bit:
 370       while (!(bi->bits & 1))
 371         {
 372           bi->bits >>= 1;
 373           *bit_no += 1;
 374         }
 375       return true;
 376     }
 377
 378   /* Round up to the word boundary.  We might have just iterated past
 379      the end of the last word, hence the -1.  It is not possible for
 380      bit_no to point at the beginning of the now last word.  */
 381   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
 382              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
 383   bi->word_no++;
 384
 385   while (1)
 386     {
 387       /* Find the next nonzero word in this elt.  */
 388       while (bi->word_no != BITMAP_ELEMENT_WORDS)
 389         {
 390           bi->bits = bi->elt1->bits[bi->word_no];
 391           if (bi->bits)
 392             goto next_bit;
 393           *bit_no += BITMAP_WORD_BITS;
 394           bi->word_no++;
 395         }
 396
 397       /* Advance to the next element.  */
 398       bi->elt1 = bi->elt1->next;
 399       if (!bi->elt1)
 400         return false;
 401       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 402       bi->word_no = 0;
 403     }
 404 }
 405
 406 /* Advance to the next nonzero bit of an intersecting pair of
 407    bitmaps.  We will have already advanced past the just iterated bit.
 408    Return true if there is a bit to iterate.  */
 409
 410 static inline bool
 411 bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
 412 {
 413   /* If our current word is nonzero, it contains the bit we want.  */
 414   if (bi->bits)
 415     {
 416     next_bit:
 417       while (!(bi->bits & 1))
 418         {
 419           bi->bits >>= 1;
 420           *bit_no += 1;
 421         }
 422       return true;
 423     }
 424
 425   /* Round up to the word boundary.  We might have just iterated past
 426      the end of the last word, hence the -1.  It is not possible for
 427      bit_no to point at the beginning of the now last word.  */
 428   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
 429              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
 430   bi->word_no++;
 431
 432   while (1)
 433     {
 434       /* Find the next nonzero word in this elt.  */
 435       while (bi->word_no != BITMAP_ELEMENT_WORDS)
 436         {
 437           bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
 438           if (bi->bits)
 439             goto next_bit;
 440           *bit_no += BITMAP_WORD_BITS;
 441           bi->word_no++;
 442         }
 443
 444       /* Advance to the next identical element.  */
 445       do
 446         {
 447           /* Advance elt1 while it is less than elt2.  We always want
 448              to advance one elt.  */
 449           do
 450             {
 451               bi->elt1 = bi->elt1->next;
 452               if (!bi->elt1)
 453                 return false;
 454             }
 455           while (bi->elt1->indx < bi->elt2->indx);
 456
 457           /* Advance elt2 to be no less than elt1.  This might not
 458              advance.  */
 459           while (bi->elt2->indx < bi->elt1->indx)
 460             {
 461               bi->elt2 = bi->elt2->next;
 462               if (!bi->elt2)
 463                 return false;
 464             }
 465         }
 466       while (bi->elt1->indx != bi->elt2->indx);
 467
 468       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 469       bi->word_no = 0;
 470     }
 471 }
 472
 473 /* Advance to the next nonzero bit in the intersection of
 474    complemented bitmaps.  We will have already advanced past the just
 475    iterated bit.  */
 476
 477 static inline bool
 478 bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
 479 {
 480   /* If our current word is nonzero, it contains the bit we want.  */
 481   if (bi->bits)
 482     {
 483     next_bit:
 484       while (!(bi->bits & 1))
 485         {
 486           bi->bits >>= 1;
 487           *bit_no += 1;
 488         }
 489       return true;
 490     }
 491
 492   /* Round up to the word boundary.  We might have just iterated past
 493      the end of the last word, hence the -1.  It is not possible for
 494      bit_no to point at the beginning of the now last word.  */
 495   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
 496              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
 497   bi->word_no++;
 498
 499   while (1)
 500     {
 501       /* Find the next nonzero word in this elt.  */
 502       while (bi->word_no != BITMAP_ELEMENT_WORDS)
 503         {
 504           bi->bits = bi->elt1->bits[bi->word_no];
 505           if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
 506             bi->bits &= ~bi->elt2->bits[bi->word_no];
 507           if (bi->bits)
 508             goto next_bit;
 509           *bit_no += BITMAP_WORD_BITS;
 510           bi->word_no++;
 511         }
 512
 513       /* Advance to the next element of elt1.  */
 514       bi->elt1 = bi->elt1->next;
 515       if (!bi->elt1)
 516         return false;
 517
 518       /* Advance elt2 until it is no less than elt1.  */
 519       while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
 520         bi->elt2 = bi->elt2->next;
 521
 522       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 523       bi->word_no = 0;
 524     }
 525 }
 526
 527 /* Loop over all bits set in BITMAP, starting with MIN and setting
 528    BITNUM to the bit number.  ITER is a bitmap iterator.  BITNUM
 529    should be treated as a read-only variable as it contains loop
 530    state.  */
 531
 532 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)             \
 533   for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM));         \
 534        bmp_iter_set (&(ITER), &(BITNUM));                               \
 535        bmp_iter_next (&(ITER), &(BITNUM)))
 536
 537 /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
 538    and setting BITNUM to the bit number.  ITER is a bitmap iterator.
 539    BITNUM should be treated as a read-only variable as it contains
 540    loop state.  */
 541
 542 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER)   \
 543   for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),         \
 544                           &(BITNUM));                                   \
 545        bmp_iter_and (&(ITER), &(BITNUM));                               \
 546        bmp_iter_next (&(ITER), &(BITNUM)))
 547
 548 /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
 549    and setting BITNUM to the bit number.  ITER is a bitmap iterator.
 550    BITNUM should be treated as a read-only variable as it contains
 551    loop state.  */
 552
 553 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
 554   for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),   \
 555                                 &(BITNUM));                             \
 556        bmp_iter_and_compl (&(ITER), &(BITNUM));                         \
 557        bmp_iter_next (&(ITER), &(BITNUM)))
 558
 559 #endif /* GCC_BITMAP_H */