bitmap.h revision 50397
150397Sobrien/* Functions to support general ended bitmaps. 250397Sobrien Copyright (C) 1997 Free Software Foundation, Inc. 350397Sobrien 450397SobrienThis file is part of GNU CC. 550397Sobrien 650397SobrienGNU CC is free software; you can redistribute it and/or modify 750397Sobrienit under the terms of the GNU General Public License as published by 850397Sobrienthe Free Software Foundation; either version 2, or (at your option) 950397Sobrienany later version. 1050397Sobrien 1150397SobrienGNU CC is distributed in the hope that it will be useful, 1250397Sobrienbut WITHOUT ANY WARRANTY; without even the implied warranty of 1350397SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1450397SobrienGNU General Public License for more details. 1550397Sobrien 1650397SobrienYou should have received a copy of the GNU General Public License 1750397Sobrienalong with GNU CC; see the file COPYING. If not, write to 1850397Sobrienthe Free Software Foundation, 59 Temple Place - Suite 330, 1950397SobrienBoston, MA 02111-1307, USA. */ 2050397Sobrien 2150397Sobrien/* Number of words to use for each element in the linked list. */ 2250397Sobrien 2350397Sobrien#ifndef BITMAP_ELEMENT_WORDS 2450397Sobrien#define BITMAP_ELEMENT_WORDS 2 2550397Sobrien#endif 2650397Sobrien 2750397Sobrien/* Number of bits in each actual element of a bitmap. We get slightly better 2850397Sobrien code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if 2950397Sobrien bits is unsigned, assuming it is a power of 2. */ 3050397Sobrien 3150397Sobrien#define BITMAP_ELEMENT_ALL_BITS \ 3250397Sobrien ((unsigned) (BITMAP_ELEMENT_WORDS * HOST_BITS_PER_WIDE_INT)) 3350397Sobrien 3450397Sobrien/* Bitmap set element. We use a linked list to hold only the bits that 3550397Sobrien are set. This allows for use to grow the bitset dynamically without 3650397Sobrien having to realloc and copy a giant bit array. The `prev' field is 3750397Sobrien undefined for an element on the free list. */ 3850397Sobrien 3950397Sobrientypedef struct bitmap_element_def 4050397Sobrien{ 4150397Sobrien struct bitmap_element_def *next; /* Next element. */ 4250397Sobrien struct bitmap_element_def *prev; /* Previous element. */ 4350397Sobrien unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */ 4450397Sobrien unsigned HOST_WIDE_INT bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */ 4550397Sobrien} bitmap_element; 4650397Sobrien 4750397Sobrien/* Head of bitmap linked list. */ 4850397Sobrientypedef struct bitmap_head_def { 4950397Sobrien bitmap_element *first; /* First element in linked list. */ 5050397Sobrien bitmap_element *current; /* Last element looked at. */ 5150397Sobrien int indx; /* Index of last element looked at. */ 5250397Sobrien} bitmap_head, *bitmap; 5350397Sobrien 5450397Sobrien/* Enumeration giving the various operations we support. */ 5550397Sobrienenum bitmap_bits { 5650397Sobrien BITMAP_AND, /* TO = FROM1 & FROM2 */ 5750397Sobrien BITMAP_AND_COMPL, /* TO = FROM1 & ~ FROM2 */ 5850397Sobrien BITMAP_IOR /* TO = FROM1 | FROM2 */ 5950397Sobrien}; 6050397Sobrien 6150397Sobrien/* Global data */ 6250397Sobrienextern bitmap_element *bitmap_free; /* Freelist of bitmap elements */ 6350397Sobrienextern bitmap_element bitmap_zero; /* Zero bitmap element */ 6450397Sobrien 6550397Sobrien/* Clear a bitmap by freeing up the linked list. */ 6650397Sobrienextern void bitmap_clear PROTO((bitmap)); 6750397Sobrien 6850397Sobrien/* Copy a bitmap to another bitmap. */ 6950397Sobrienextern void bitmap_copy PROTO((bitmap, bitmap)); 7050397Sobrien 7150397Sobrien/* Perform an operation on two bitmaps, yielding a third. */ 7250397Sobrienextern void bitmap_operation PROTO((bitmap, bitmap, bitmap, enum bitmap_bits)); 7350397Sobrien 7450397Sobrien/* `or' into one bitmap the `and' of a second bitmap witih the complement 7550397Sobrien of a third. */ 7650397Sobrienextern void bitmap_ior_and_compl PROTO((bitmap, bitmap, bitmap)); 7750397Sobrien 7850397Sobrien/* Clear a single register in a register set. */ 7950397Sobrienextern void bitmap_clear_bit PROTO((bitmap, int)); 8050397Sobrien 8150397Sobrien/* Set a single register in a register set. */ 8250397Sobrienextern void bitmap_set_bit PROTO((bitmap, int)); 8350397Sobrien 8450397Sobrien/* Return true if a register is set in a register set. */ 8550397Sobrienextern int bitmap_bit_p PROTO((bitmap, int)); 8650397Sobrien 8750397Sobrien/* Debug functions to print a bitmap linked list. */ 8850397Sobrienextern void bitmap_debug PROTO((bitmap)); 8950397Sobrienextern void bitmap_debug_file PROTO((FILE *, bitmap)); 9050397Sobrien 9150397Sobrien/* Print a bitmap */ 9250397Sobrienextern void bitmap_print PROTO((FILE *, bitmap, char *, char *)); 9350397Sobrien 9450397Sobrien/* Initialize a bitmap header. */ 9550397Sobrienextern bitmap bitmap_initialize PROTO((bitmap)); 9650397Sobrien 9750397Sobrien/* Release all memory held by bitmaps. */ 9850397Sobrienextern void bitmap_release_memory PROTO((void)); 9950397Sobrien 10050397Sobrienextern void debug_bitmap PROTO((bitmap)); 10150397Sobrien 10250397Sobrien/* Allocate a bitmap with oballoc. */ 10350397Sobrien#define BITMAP_OBSTACK_ALLOC(OBSTACK) \ 10450397Sobrien bitmap_initialize ((bitmap) obstack_alloc (OBSTACK, sizeof (bitmap_head))) 10550397Sobrien 10650397Sobrien/* Allocate a bitmap with alloca. */ 10750397Sobrien#define BITMAP_ALLOCA() \ 10850397Sobrien bitmap_initialize ((bitmap) alloca (sizeof (bitmap_head))) 10950397Sobrien 11050397Sobrien/* Do any cleanup needed on a bitmap when it is no longer used. */ 11150397Sobrien#define BITMAP_FREE(BITMAP) \ 11250397Sobriendo { \ 11350397Sobrien if (BITMAP) \ 11450397Sobrien { \ 11550397Sobrien bitmap_clear (BITMAP); \ 11650397Sobrien (BITMAP) = 0; \ 11750397Sobrien } \ 11850397Sobrien} while (0) 11950397Sobrien 12050397Sobrien/* Do any one-time initializations needed for bitmaps. */ 12150397Sobrien#define BITMAP_INIT_ONCE() 12250397Sobrien 12350397Sobrien/* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the 12450397Sobrien bit number and executing CODE for all bits that are set. */ 12550397Sobrien 12650397Sobrien#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE) \ 12750397Sobriendo { \ 12850397Sobrien bitmap_element *ptr_ = (BITMAP)->first; \ 12950397Sobrien unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 13050397Sobrien unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT); \ 13150397Sobrien unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT)) \ 13250397Sobrien % BITMAP_ELEMENT_WORDS); \ 13350397Sobrien \ 13450397Sobrien \ 13550397Sobrien /* Find the block the minimum bit is in. */ \ 13650397Sobrien while (ptr_ != 0 && ptr_->indx < indx_) \ 13750397Sobrien ptr_ = ptr_->next; \ 13850397Sobrien \ 13950397Sobrien if (ptr_ != 0 && ptr_->indx != indx_) \ 14050397Sobrien { \ 14150397Sobrien bit_num_ = 0; \ 14250397Sobrien word_num_ = 0; \ 14350397Sobrien } \ 14450397Sobrien \ 14550397Sobrien for (; ptr_ != 0; ptr_ = ptr_->next) \ 14650397Sobrien { \ 14750397Sobrien for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 14850397Sobrien { \ 14950397Sobrien unsigned HOST_WIDE_INT word_ = ptr_->bits[word_num_]; \ 15050397Sobrien \ 15150397Sobrien if (word_ != 0) \ 15250397Sobrien { \ 15350397Sobrien for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++) \ 15450397Sobrien { \ 15550397Sobrien unsigned HOST_WIDE_INT mask_ \ 15650397Sobrien = ((unsigned HOST_WIDE_INT) 1) << bit_num_; \ 15750397Sobrien \ 15850397Sobrien if ((word_ & mask_) != 0) \ 15950397Sobrien { \ 16050397Sobrien word_ &= ~ mask_; \ 16150397Sobrien (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS \ 16250397Sobrien + word_num_ * HOST_BITS_PER_WIDE_INT \ 16350397Sobrien + bit_num_); \ 16450397Sobrien CODE; \ 16550397Sobrien \ 16650397Sobrien if (word_ == 0) \ 16750397Sobrien break; \ 16850397Sobrien } \ 16950397Sobrien } \ 17050397Sobrien } \ 17150397Sobrien \ 17250397Sobrien bit_num_ = 0; \ 17350397Sobrien } \ 17450397Sobrien \ 17550397Sobrien word_num_ = 0; \ 17650397Sobrien } \ 17750397Sobrien} while (0) 17850397Sobrien 17950397Sobrien/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting 18050397Sobrien BITNUM to the bit number and executing CODE for all bits that are set in 18150397Sobrien the first bitmap and not set in the second. */ 18250397Sobrien 18350397Sobrien#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ 18450397Sobriendo { \ 18550397Sobrien bitmap_element *ptr1_ = (BITMAP1)->first; \ 18650397Sobrien bitmap_element *ptr2_ = (BITMAP2)->first; \ 18750397Sobrien unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 18850397Sobrien unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT); \ 18950397Sobrien unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT)) \ 19050397Sobrien % BITMAP_ELEMENT_WORDS); \ 19150397Sobrien \ 19250397Sobrien /* Find the block the minimum bit is in in the first bitmap. */ \ 19350397Sobrien while (ptr1_ != 0 && ptr1_->indx < indx_) \ 19450397Sobrien ptr1_ = ptr1_->next; \ 19550397Sobrien \ 19650397Sobrien if (ptr1_ != 0 && ptr1_->indx != indx_) \ 19750397Sobrien { \ 19850397Sobrien bit_num_ = 0; \ 19950397Sobrien word_num_ = 0; \ 20050397Sobrien } \ 20150397Sobrien \ 20250397Sobrien for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \ 20350397Sobrien { \ 20450397Sobrien /* Advance BITMAP2 to the equivalent link, using an all \ 20550397Sobrien zero element if an equivalent link doesn't exist. */ \ 20650397Sobrien bitmap_element *tmp2_; \ 20750397Sobrien \ 20850397Sobrien while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \ 20950397Sobrien ptr2_ = ptr2_->next; \ 21050397Sobrien \ 21150397Sobrien tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx) \ 21250397Sobrien ? ptr2_ : &bitmap_zero); \ 21350397Sobrien \ 21450397Sobrien for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 21550397Sobrien { \ 21650397Sobrien unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_] \ 21750397Sobrien & ~ tmp2_->bits[word_num_]); \ 21850397Sobrien if (word_ != 0) \ 21950397Sobrien { \ 22050397Sobrien for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++) \ 22150397Sobrien { \ 22250397Sobrien unsigned HOST_WIDE_INT mask_ \ 22350397Sobrien = ((unsigned HOST_WIDE_INT)1) << bit_num_; \ 22450397Sobrien \ 22550397Sobrien if ((word_ & mask_) != 0) \ 22650397Sobrien { \ 22750397Sobrien word_ &= ~ mask_; \ 22850397Sobrien (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \ 22950397Sobrien + word_num_ * HOST_BITS_PER_WIDE_INT \ 23050397Sobrien + bit_num_); \ 23150397Sobrien \ 23250397Sobrien CODE; \ 23350397Sobrien if (word_ == 0) \ 23450397Sobrien break; \ 23550397Sobrien } \ 23650397Sobrien } \ 23750397Sobrien } \ 23850397Sobrien \ 23950397Sobrien bit_num_ = 0; \ 24050397Sobrien } \ 24150397Sobrien \ 24250397Sobrien word_num_ = 0; \ 24350397Sobrien } \ 24450397Sobrien} while (0) 24550397Sobrien 24650397Sobrien/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting 24750397Sobrien BITNUM to the bit number and executing CODE for all bits that are set in 24850397Sobrien the both bitmaps. */ 24950397Sobrien 25050397Sobrien#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ 25150397Sobriendo { \ 25250397Sobrien bitmap_element *ptr1_ = (BITMAP1)->first; \ 25350397Sobrien bitmap_element *ptr2_ = (BITMAP2)->first; \ 25450397Sobrien unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 25550397Sobrien unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT); \ 25650397Sobrien unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT)) \ 25750397Sobrien % BITMAP_ELEMENT_WORDS); \ 25850397Sobrien \ 25950397Sobrien /* Find the block the minimum bit is in in the first bitmap. */ \ 26050397Sobrien while (ptr1_ != 0 && ptr1_->indx < indx_) \ 26150397Sobrien ptr1_ = ptr1_->next; \ 26250397Sobrien \ 26350397Sobrien if (ptr1_ != 0 && ptr1_->indx != indx_) \ 26450397Sobrien { \ 26550397Sobrien bit_num_ = 0; \ 26650397Sobrien word_num_ = 0; \ 26750397Sobrien } \ 26850397Sobrien \ 26950397Sobrien for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \ 27050397Sobrien { \ 27150397Sobrien /* Advance BITMAP2 to the equivalent link */ \ 27250397Sobrien while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \ 27350397Sobrien ptr2_ = ptr2_->next; \ 27450397Sobrien \ 27550397Sobrien if (ptr2_ == 0) \ 27650397Sobrien { \ 27750397Sobrien /* If there are no more elements in BITMAP2, exit loop now.*/ \ 27850397Sobrien ptr1_ = (bitmap_element *)0; \ 27950397Sobrien break; \ 28050397Sobrien } \ 28150397Sobrien else if (ptr2_->indx > ptr1_->indx) \ 28250397Sobrien { \ 28350397Sobrien bit_num_ = word_num_ = 0; \ 28450397Sobrien continue; \ 28550397Sobrien } \ 28650397Sobrien \ 28750397Sobrien for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 28850397Sobrien { \ 28950397Sobrien unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_] \ 29050397Sobrien & ptr2_->bits[word_num_]); \ 29150397Sobrien if (word_ != 0) \ 29250397Sobrien { \ 29350397Sobrien for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++) \ 29450397Sobrien { \ 29550397Sobrien unsigned HOST_WIDE_INT mask_ \ 29650397Sobrien = ((unsigned HOST_WIDE_INT)1) << bit_num_; \ 29750397Sobrien \ 29850397Sobrien if ((word_ & mask_) != 0) \ 29950397Sobrien { \ 30050397Sobrien word_ &= ~ mask_; \ 30150397Sobrien (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \ 30250397Sobrien + word_num_ * HOST_BITS_PER_WIDE_INT \ 30350397Sobrien + bit_num_); \ 30450397Sobrien \ 30550397Sobrien CODE; \ 30650397Sobrien if (word_ == 0) \ 30750397Sobrien break; \ 30850397Sobrien } \ 30950397Sobrien } \ 31050397Sobrien } \ 31150397Sobrien \ 31250397Sobrien bit_num_ = 0; \ 31350397Sobrien } \ 31450397Sobrien \ 31550397Sobrien word_num_ = 0; \ 31650397Sobrien } \ 31750397Sobrien} while (0) 318