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