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