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