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