bitmap.h revision 117395
1139749Simp/* Functions to support general ended bitmaps. 250702Swpaul Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003 350702Swpaul Free Software Foundation, Inc. 450702Swpaul 550702SwpaulThis file is part of GCC. 650702Swpaul 750702SwpaulGCC is free software; you can redistribute it and/or modify it under 850702Swpaulthe terms of the GNU General Public License as published by the Free 950702SwpaulSoftware Foundation; either version 2, or (at your option) any later 1050702Swpaulversion. 1150702Swpaul 1250702SwpaulGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1350702SwpaulWARRANTY; without even the implied warranty of MERCHANTABILITY or 1450702SwpaulFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1550702Swpaulfor more details. 1650702Swpaul 1750702SwpaulYou should have received a copy of the GNU General Public License 1850702Swpaulalong with GCC; see the file COPYING. If not, write to the Free 1950702SwpaulSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 2050702Swpaul02111-1307, USA. */ 2150702Swpaul 2250702Swpaul#ifndef GCC_BITMAP_H 2350702Swpaul#define GCC_BITMAP_H 2450702Swpaul 2550702Swpaul/* Fundamental storage type for bitmap. */ 2650702Swpaul 2750702Swpaul/* typedef unsigned HOST_WIDE_INT BITMAP_WORD; */ 2850702Swpaul/* #define nBITMAP_WORD_BITS HOST_BITS_PER_WIDE_INT */ 2950702Swpaultypedef unsigned long BITMAP_WORD; 3050702Swpaul#define nBITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG) 3150702Swpaul#define BITMAP_WORD_BITS (unsigned) nBITMAP_WORD_BITS 3250702Swpaul 33119418Sobrien/* Number of words to use for each element in the linked list. */ 34119418Sobrien 35119418Sobrien#ifndef BITMAP_ELEMENT_WORDS 3650702Swpaul#define BITMAP_ELEMENT_WORDS ((128 + nBITMAP_WORD_BITS - 1) / nBITMAP_WORD_BITS) 3750702Swpaul#endif 3850702Swpaul 3950702Swpaul/* Number of bits in each actual element of a bitmap. We get slightly better 4050702Swpaul code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if 4150702Swpaul bits is unsigned, assuming it is a power of 2. */ 4250702Swpaul 43129876Sphk#define BITMAP_ELEMENT_ALL_BITS \ 4450702Swpaul ((unsigned) (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)) 4550702Swpaul 46257184Sglebius/* Bitmap set element. We use a linked list to hold only the bits that 4750702Swpaul are set. This allows for use to grow the bitset dynamically without 4850702Swpaul having to realloc and copy a giant bit array. The `prev' field is 4994149Swpaul undefined for an element on the free list. */ 5050702Swpaul 5150702Swpaultypedef struct bitmap_element_def GTY(()) 5250702Swpaul{ 5350702Swpaul struct bitmap_element_def *next; /* Next element. */ 54109514Sobrien struct bitmap_element_def *prev; /* Previous element. */ 5550702Swpaul unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */ 5694149Swpaul BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */ 57271864Sglebius} bitmap_element; 5894149Swpaul 5950702Swpaul/* Head of bitmap linked list. */ 6050702Swpaultypedef struct bitmap_head_def GTY(()) { 61105135Salfred bitmap_element *first; /* First element in linked list. */ 62105135Salfred bitmap_element *current; /* Last element looked at. */ 6350702Swpaul unsigned int indx; /* Index of last element looked at. */ 6450702Swpaul int using_obstack; /* Are we using an obstack or ggc for 6550702Swpaul allocation? */ 6650702Swpaul} bitmap_head; 6750702Swpaultypedef struct bitmap_head_def *bitmap; 6895722Sphk 6950702Swpaul/* Enumeration giving the various operations we support. */ 70227908Smariusenum bitmap_bits { 7150702Swpaul BITMAP_AND, /* TO = FROM1 & FROM2 */ 7250702Swpaul BITMAP_AND_COMPL, /* TO = FROM1 & ~ FROM2 */ 7350702Swpaul BITMAP_IOR, /* TO = FROM1 | FROM2 */ 7450702Swpaul BITMAP_XOR, /* TO = FROM1 ^ FROM2 */ 7550702Swpaul BITMAP_IOR_COMPL /* TO = FROM1 | ~FROM2 */ 7650702Swpaul}; 7750702Swpaul 78221407Smarius/* Global data */ 7950702Swpaulextern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ 8050702Swpaul 8150702Swpaul/* Clear a bitmap by freeing up the linked list. */ 8250702Swpaulextern void bitmap_clear PARAMS ((bitmap)); 8392739Salfred 8494149Swpaul/* Copy a bitmap to another bitmap. */ 8550702Swpaulextern void bitmap_copy PARAMS ((bitmap, bitmap)); 86165991Smarius 87165991Smarius/* True if two bitmaps are identical. */ 88165991Smariusextern int bitmap_equal_p PARAMS ((bitmap, bitmap)); 89165991Smarius 90165991Smarius/* Perform an operation on two bitmaps, yielding a third. */ 91165991Smariusextern int bitmap_operation PARAMS ((bitmap, bitmap, bitmap, enum bitmap_bits)); 92165991Smarius 93165991Smarius/* `or' into one bitmap the `and' of a second bitmap witih the complement 94165991Smarius of a third. */ 95164827Smariusextern void bitmap_ior_and_compl PARAMS ((bitmap, bitmap, bitmap)); 96221407Smarius 97221407Smarius/* Clear a single register in a register set. */ 98221407Smariusextern void bitmap_clear_bit PARAMS ((bitmap, int)); 99164827Smarius 100164827Smarius/* Set a single register in a register set. */ 101164827Smariusextern void bitmap_set_bit PARAMS ((bitmap, int)); 102221407Smarius 103221407Smarius/* Return true if a register is set in a register set. */ 104221407Smariusextern int bitmap_bit_p PARAMS ((bitmap, int)); 105221407Smarius 106221407Smarius/* Debug functions to print a bitmap linked list. */ 107221407Smariusextern void debug_bitmap PARAMS ((bitmap)); 108105135Salfredextern void debug_bitmap_file PARAMS ((FILE *, bitmap)); 109150763Simp 11050702Swpaul/* Print a bitmap */ 111164827Smariusextern void bitmap_print PARAMS ((FILE *, bitmap, const char *, const char *)); 11250702Swpaul 113164827Smarius/* Initialize a bitmap header. If HEAD is NULL, a new header will be 114164827Smarius allocated. USING_OBSTACK indicates how elements should be allocated. */ 115164827Smariusextern bitmap bitmap_initialize PARAMS ((bitmap head, 11650702Swpaul int using_obstack)); 117277093Sglebius 118165991Smarius/* Release all memory used by the bitmap obstack. */ 119165991Smariusextern void bitmap_release_memory PARAMS ((void)); 12050702Swpaul 12150702Swpaul/* A few compatibility/functions macros for compatibility with sbitmaps */ 122105135Salfred#define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n") 123150763Simp#define bitmap_zero(a) bitmap_clear (a) 12450702Swpaul#define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR) 12550702Swpaul#define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND) 126213364Smariusextern int bitmap_union_of_diff PARAMS((bitmap, bitmap, bitmap, bitmap)); 127213364Smariusextern int bitmap_first_set_bit PARAMS((bitmap)); 128213364Smariusextern int bitmap_last_set_bit PARAMS((bitmap)); 129221407Smarius 130221407Smarius/* Allocate a bitmap with oballoc. */ 131164711Smarius#define BITMAP_OBSTACK_ALLOC(OBSTACK) \ 13250702Swpaul bitmap_initialize ((bitmap) obstack_alloc (OBSTACK, sizeof (bitmap_head)), 1) 13350702Swpaul 13484145Sjlemon/* Allocate a bitmap with ggc_alloc. */ 135150763Simp#define BITMAP_GGC_ALLOC() \ 13650702Swpaul bitmap_initialize (NULL, 0) 13750702Swpaul 13850702Swpaul/* Allocate a bitmap with xmalloc. */ 13950702Swpaul#define BITMAP_XMALLOC() \ 14050702Swpaul bitmap_initialize ((bitmap) xmalloc (sizeof (bitmap_head)), 1) 14150702Swpaul 14250702Swpaul/* Do any cleanup needed on a bitmap when it is no longer used. */ 143164711Smarius#define BITMAP_FREE(BITMAP) \ 14450702Swpauldo { \ 14550702Swpaul if (BITMAP) \ 14650702Swpaul { \ 14750702Swpaul bitmap_clear (BITMAP); \ 14850702Swpaul (BITMAP) = 0; \ 14950702Swpaul } \ 15050702Swpaul} while (0) 15150702Swpaul 15250702Swpaul/* Do any cleanup needed on an xmalloced bitmap when it is no longer used. */ 15350702Swpaul#define BITMAP_XFREE(BITMAP) \ 15450702Swpauldo { \ 155221407Smarius if (BITMAP) \ 15650702Swpaul { \ 15750702Swpaul bitmap_clear (BITMAP); \ 15884145Sjlemon free (BITMAP); \ 15950702Swpaul (BITMAP) = 0; \ 16050702Swpaul } \ 16194149Swpaul} while (0) 162104094Sphk 163150763Simp/* Do any one-time initializations needed for bitmaps. */ 16494149Swpaul#define BITMAP_INIT_ONCE() 16594149Swpaul 166164711Smarius/* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the 16794149Swpaul bit number and executing CODE for all bits that are set. */ 16894149Swpaul 16994149Swpaul#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE) \ 17094149Swpauldo { \ 17194149Swpaul bitmap_element *ptr_ = (BITMAP)->first; \ 17294149Swpaul unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 17394149Swpaul unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \ 17494149Swpaul unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \ 17594149Swpaul \ 17694149Swpaul \ 17794149Swpaul /* Find the block the minimum bit is in. */ \ 17894149Swpaul while (ptr_ != 0 && ptr_->indx < indx_) \ 17994149Swpaul ptr_ = ptr_->next; \ 18094149Swpaul \ 18194149Swpaul if (ptr_ != 0 && ptr_->indx != indx_) \ 18294149Swpaul { \ 18394149Swpaul bit_num_ = 0; \ 18494149Swpaul word_num_ = 0; \ 18594149Swpaul } \ 18694149Swpaul \ 18794149Swpaul for (; ptr_ != 0; ptr_ = ptr_->next) \ 18894149Swpaul { \ 18994149Swpaul for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 19094149Swpaul { \ 19194149Swpaul BITMAP_WORD word_ = ptr_->bits[word_num_]; \ 19294149Swpaul \ 19394149Swpaul if (word_ != 0) \ 19494149Swpaul { \ 19594149Swpaul for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \ 19694149Swpaul { \ 19794149Swpaul BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \ 19894149Swpaul \ 19994149Swpaul if ((word_ & mask_) != 0) \ 200173665Syongari { \ 201173665Syongari word_ &= ~ mask_; \ 202173665Syongari (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS \ 203213384Smarius + word_num_ * BITMAP_WORD_BITS \ 20494149Swpaul + bit_num_); \ 205213384Smarius CODE; \ 20694149Swpaul \ 20794149Swpaul if (word_ == 0) \ 20894149Swpaul break; \ 209213384Smarius } \ 21094149Swpaul } \ 211164711Smarius } \ 212221407Smarius \ 213221407Smarius bit_num_ = 0; \ 214221407Smarius } \ 21594149Swpaul \ 21694149Swpaul word_num_ = 0; \ 21794149Swpaul } \ 21894149Swpaul} while (0) 21994149Swpaul 220164711Smarius/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting 22194149Swpaul BITNUM to the bit number and executing CODE for all bits that are set in 22294149Swpaul the first bitmap and not set in the second. */ 22394149Swpaul 22494149Swpaul#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ 22594149Swpauldo { \ 22694149Swpaul bitmap_element *ptr1_ = (BITMAP1)->first; \ 22794149Swpaul bitmap_element *ptr2_ = (BITMAP2)->first; \ 22894149Swpaul unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 22994149Swpaul unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \ 23094149Swpaul unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \ 23194149Swpaul \ 23294149Swpaul /* Find the block the minimum bit is in in the first bitmap. */ \ 23394149Swpaul while (ptr1_ != 0 && ptr1_->indx < indx_) \ 23494149Swpaul ptr1_ = ptr1_->next; \ 235221407Smarius \ 236221407Smarius if (ptr1_ != 0 && ptr1_->indx != indx_) \ 237221407Smarius { \ 238221407Smarius bit_num_ = 0; \ 23994149Swpaul word_num_ = 0; \ 24094149Swpaul } \ 24194149Swpaul \ 24294149Swpaul for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \ 24394149Swpaul { \ 244221407Smarius /* Advance BITMAP2 to the equivalent link, using an all \ 24594149Swpaul zero element if an equivalent link doesn't exist. */ \ 24694149Swpaul bitmap_element *tmp2_; \ 24794149Swpaul \ 24894149Swpaul while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \ 24994149Swpaul ptr2_ = ptr2_->next; \ 25094149Swpaul \ 25194149Swpaul tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx) \ 25294149Swpaul ? ptr2_ : &bitmap_zero_bits); \ 25394149Swpaul \ 25494149Swpaul for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 25594149Swpaul { \ 256213384Smarius BITMAP_WORD word_ = (ptr1_->bits[word_num_] \ 25794149Swpaul & ~ tmp2_->bits[word_num_]); \ 258164711Smarius if (word_ != 0) \ 25994149Swpaul { \ 260 for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \ 261 { \ 262 BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \ 263 \ 264 if ((word_ & mask_) != 0) \ 265 { \ 266 word_ &= ~ mask_; \ 267 (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \ 268 + word_num_ * BITMAP_WORD_BITS \ 269 + bit_num_); \ 270 \ 271 CODE; \ 272 if (word_ == 0) \ 273 break; \ 274 } \ 275 } \ 276 } \ 277 \ 278 bit_num_ = 0; \ 279 } \ 280 \ 281 word_num_ = 0; \ 282 } \ 283} while (0) 284 285/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting 286 BITNUM to the bit number and executing CODE for all bits that are set in 287 the both bitmaps. */ 288 289#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ 290do { \ 291 bitmap_element *ptr1_ = (BITMAP1)->first; \ 292 bitmap_element *ptr2_ = (BITMAP2)->first; \ 293 unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 294 unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \ 295 unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \ 296 \ 297 /* Find the block the minimum bit is in in the first bitmap. */ \ 298 while (ptr1_ != 0 && ptr1_->indx < indx_) \ 299 ptr1_ = ptr1_->next; \ 300 \ 301 if (ptr1_ != 0 && ptr1_->indx != indx_) \ 302 { \ 303 bit_num_ = 0; \ 304 word_num_ = 0; \ 305 } \ 306 \ 307 for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \ 308 { \ 309 /* Advance BITMAP2 to the equivalent link */ \ 310 while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \ 311 ptr2_ = ptr2_->next; \ 312 \ 313 if (ptr2_ == 0) \ 314 { \ 315 /* If there are no more elements in BITMAP2, exit loop now. */ \ 316 ptr1_ = (bitmap_element *)0; \ 317 break; \ 318 } \ 319 else if (ptr2_->indx > ptr1_->indx) \ 320 { \ 321 bit_num_ = word_num_ = 0; \ 322 continue; \ 323 } \ 324 \ 325 for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 326 { \ 327 BITMAP_WORD word_ = (ptr1_->bits[word_num_] \ 328 & ptr2_->bits[word_num_]); \ 329 if (word_ != 0) \ 330 { \ 331 for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \ 332 { \ 333 BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \ 334 \ 335 if ((word_ & mask_) != 0) \ 336 { \ 337 word_ &= ~ mask_; \ 338 (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \ 339 + word_num_ * BITMAP_WORD_BITS \ 340 + bit_num_); \ 341 \ 342 CODE; \ 343 if (word_ == 0) \ 344 break; \ 345 } \ 346 } \ 347 } \ 348 \ 349 bit_num_ = 0; \ 350 } \ 351 \ 352 word_num_ = 0; \ 353 } \ 354} while (0) 355 356#endif /* GCC_BITMAP_H */ 357