bitmap.h revision 90075
150397Sobrien/* Functions to support general ended bitmaps. 290075Sobrien Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002 390075Sobrien Free Software Foundation, Inc. 450397Sobrien 590075SobrienThis file is part of GCC. 650397Sobrien 790075SobrienGCC is free software; you can redistribute it and/or modify it under 890075Sobrienthe terms of the GNU General Public License as published by the Free 990075SobrienSoftware Foundation; either version 2, or (at your option) any later 1090075Sobrienversion. 1150397Sobrien 1290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1590075Sobrienfor more details. 1650397Sobrien 1750397SobrienYou should have received a copy of the GNU General Public License 1890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 1990075SobrienSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 2090075Sobrien02111-1307, USA. */ 2150397Sobrien 2290075Sobrien#ifndef GCC_BITMAP_H 2390075Sobrien#define GCC_BITMAP_H 2490075Sobrien 2550397Sobrien/* Number of words to use for each element in the linked list. */ 2650397Sobrien 2750397Sobrien#ifndef BITMAP_ELEMENT_WORDS 2850397Sobrien#define BITMAP_ELEMENT_WORDS 2 2950397Sobrien#endif 3050397Sobrien 3150397Sobrien/* Number of bits in each actual element of a bitmap. We get slightly better 3250397Sobrien code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if 3350397Sobrien bits is unsigned, assuming it is a power of 2. */ 3450397Sobrien 3550397Sobrien#define BITMAP_ELEMENT_ALL_BITS \ 3650397Sobrien ((unsigned) (BITMAP_ELEMENT_WORDS * HOST_BITS_PER_WIDE_INT)) 3750397Sobrien 3850397Sobrien/* Bitmap set element. We use a linked list to hold only the bits that 3950397Sobrien are set. This allows for use to grow the bitset dynamically without 4050397Sobrien having to realloc and copy a giant bit array. The `prev' field is 4150397Sobrien undefined for an element on the free list. */ 4250397Sobrien 4350397Sobrientypedef struct bitmap_element_def 4450397Sobrien{ 4590075Sobrien struct bitmap_element_def *next; /* Next element. */ 4690075Sobrien struct bitmap_element_def *prev; /* Previous element. */ 4790075Sobrien unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */ 4890075Sobrien unsigned HOST_WIDE_INT bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */ 4950397Sobrien} bitmap_element; 5050397Sobrien 5150397Sobrien/* Head of bitmap linked list. */ 5250397Sobrientypedef struct bitmap_head_def { 5390075Sobrien bitmap_element *first; /* First element in linked list. */ 5490075Sobrien bitmap_element *current; /* Last element looked at. */ 5590075Sobrien unsigned int indx; /* Index of last element looked at. */ 5690075Sobrien 5750397Sobrien} bitmap_head, *bitmap; 5850397Sobrien 5950397Sobrien/* Enumeration giving the various operations we support. */ 6050397Sobrienenum bitmap_bits { 6150397Sobrien BITMAP_AND, /* TO = FROM1 & FROM2 */ 6250397Sobrien BITMAP_AND_COMPL, /* TO = FROM1 & ~ FROM2 */ 6390075Sobrien BITMAP_IOR, /* TO = FROM1 | FROM2 */ 6490075Sobrien BITMAP_XOR, /* TO = FROM1 ^ FROM2 */ 6590075Sobrien BITMAP_IOR_COMPL /* TO = FROM1 | ~FROM2 */ 6650397Sobrien}; 6750397Sobrien 6850397Sobrien/* Global data */ 6990075Sobrienextern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ 7050397Sobrien 7150397Sobrien/* Clear a bitmap by freeing up the linked list. */ 7290075Sobrienextern void bitmap_clear PARAMS ((bitmap)); 7350397Sobrien 7490075Sobrien/* Copy a bitmap to another bitmap. */ 7590075Sobrienextern void bitmap_copy PARAMS ((bitmap, bitmap)); 7650397Sobrien 7790075Sobrien/* True if two bitmaps are identical. */ 7890075Sobrienextern int bitmap_equal_p PARAMS ((bitmap, bitmap)); 7990075Sobrien 8050397Sobrien/* Perform an operation on two bitmaps, yielding a third. */ 8190075Sobrienextern int bitmap_operation PARAMS ((bitmap, bitmap, bitmap, enum bitmap_bits)); 8250397Sobrien 8350397Sobrien/* `or' into one bitmap the `and' of a second bitmap witih the complement 8450397Sobrien of a third. */ 8590075Sobrienextern void bitmap_ior_and_compl PARAMS ((bitmap, bitmap, bitmap)); 8650397Sobrien 8750397Sobrien/* Clear a single register in a register set. */ 8890075Sobrienextern void bitmap_clear_bit PARAMS ((bitmap, int)); 8950397Sobrien 9050397Sobrien/* Set a single register in a register set. */ 9190075Sobrienextern void bitmap_set_bit PARAMS ((bitmap, int)); 9250397Sobrien 9350397Sobrien/* Return true if a register is set in a register set. */ 9490075Sobrienextern int bitmap_bit_p PARAMS ((bitmap, int)); 9550397Sobrien 9650397Sobrien/* Debug functions to print a bitmap linked list. */ 9790075Sobrienextern void debug_bitmap PARAMS ((bitmap)); 9890075Sobrienextern void debug_bitmap_file PARAMS ((FILE *, bitmap)); 9950397Sobrien 10050397Sobrien/* Print a bitmap */ 10190075Sobrienextern void bitmap_print PARAMS ((FILE *, bitmap, const char *, const char *)); 10250397Sobrien 10350397Sobrien/* Initialize a bitmap header. */ 10490075Sobrienextern bitmap bitmap_initialize PARAMS ((bitmap)); 10550397Sobrien 10650397Sobrien/* Release all memory held by bitmaps. */ 10790075Sobrienextern void bitmap_release_memory PARAMS ((void)); 10850397Sobrien 10990075Sobrien/* A few compatibility/functions macros for compatibility with sbitmaps */ 11090075Sobrien#define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n") 11190075Sobrien#define bitmap_zero(a) bitmap_clear (a) 11290075Sobrien#define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR) 11390075Sobrien#define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND) 11490075Sobrienextern int bitmap_union_of_diff PARAMS((bitmap, bitmap, bitmap, bitmap)); 11590075Sobrienextern int bitmap_first_set_bit PARAMS((bitmap)); 11690075Sobrienextern int bitmap_last_set_bit PARAMS((bitmap)); 11750397Sobrien 11850397Sobrien/* Allocate a bitmap with oballoc. */ 11950397Sobrien#define BITMAP_OBSTACK_ALLOC(OBSTACK) \ 12050397Sobrien bitmap_initialize ((bitmap) obstack_alloc (OBSTACK, sizeof (bitmap_head))) 12150397Sobrien 12290075Sobrien/* Allocate a bitmap with alloca. Note alloca cannot be passed as an 12390075Sobrien argument to a function, so we set a temporary variable to the value 12490075Sobrien returned by alloca and pass that variable to bitmap_initialize(). 12590075Sobrien PTR is then set to the value returned from bitmap_initialize() to 12690075Sobrien avoid having it appear more than once in case it has side effects. */ 12790075Sobrien#define BITMAP_ALLOCA(PTR) \ 12890075Sobriendo { \ 12990075Sobrien bitmap temp_bitmap_ = (bitmap) alloca (sizeof (bitmap_head)); \ 13090075Sobrien (PTR) = bitmap_initialize (temp_bitmap_); \ 13190075Sobrien} while (0) 13290075Sobrien 13390075Sobrien/* Allocate a bitmap with xmalloc. */ 13490075Sobrien#define BITMAP_XMALLOC() \ 13590075Sobrien bitmap_initialize ((bitmap) xmalloc (sizeof (bitmap_head))) 13650397Sobrien 13750397Sobrien/* Do any cleanup needed on a bitmap when it is no longer used. */ 13890075Sobrien#define BITMAP_FREE(BITMAP) \ 13990075Sobriendo { \ 14090075Sobrien if (BITMAP) \ 14190075Sobrien { \ 14290075Sobrien bitmap_clear (BITMAP); \ 14390075Sobrien (BITMAP) = 0; \ 14490075Sobrien } \ 14550397Sobrien} while (0) 14650397Sobrien 14790075Sobrien/* Do any cleanup needed on an xmalloced bitmap when it is no longer used. */ 14890075Sobrien#define BITMAP_XFREE(BITMAP) \ 14990075Sobriendo { \ 15090075Sobrien if (BITMAP) \ 15190075Sobrien { \ 15290075Sobrien bitmap_clear (BITMAP); \ 15390075Sobrien free (BITMAP); \ 15490075Sobrien (BITMAP) = 0; \ 15590075Sobrien } \ 15690075Sobrien} while (0) 15790075Sobrien 15850397Sobrien/* Do any one-time initializations needed for bitmaps. */ 15950397Sobrien#define BITMAP_INIT_ONCE() 16050397Sobrien 16150397Sobrien/* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the 16290075Sobrien bit number and executing CODE for all bits that are set. */ 16350397Sobrien 16450397Sobrien#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE) \ 16550397Sobriendo { \ 16650397Sobrien bitmap_element *ptr_ = (BITMAP)->first; \ 16750397Sobrien unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 16850397Sobrien unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT); \ 16950397Sobrien unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT)) \ 17050397Sobrien % BITMAP_ELEMENT_WORDS); \ 17150397Sobrien \ 17250397Sobrien \ 17350397Sobrien /* Find the block the minimum bit is in. */ \ 17450397Sobrien while (ptr_ != 0 && ptr_->indx < indx_) \ 17550397Sobrien ptr_ = ptr_->next; \ 17650397Sobrien \ 17750397Sobrien if (ptr_ != 0 && ptr_->indx != indx_) \ 17850397Sobrien { \ 17950397Sobrien bit_num_ = 0; \ 18050397Sobrien word_num_ = 0; \ 18150397Sobrien } \ 18250397Sobrien \ 18350397Sobrien for (; ptr_ != 0; ptr_ = ptr_->next) \ 18450397Sobrien { \ 18550397Sobrien for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 18650397Sobrien { \ 18750397Sobrien unsigned HOST_WIDE_INT word_ = ptr_->bits[word_num_]; \ 18850397Sobrien \ 18950397Sobrien if (word_ != 0) \ 19050397Sobrien { \ 19150397Sobrien for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++) \ 19250397Sobrien { \ 19350397Sobrien unsigned HOST_WIDE_INT mask_ \ 19450397Sobrien = ((unsigned HOST_WIDE_INT) 1) << bit_num_; \ 19550397Sobrien \ 19650397Sobrien if ((word_ & mask_) != 0) \ 19750397Sobrien { \ 19850397Sobrien word_ &= ~ mask_; \ 19950397Sobrien (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS \ 20050397Sobrien + word_num_ * HOST_BITS_PER_WIDE_INT \ 20150397Sobrien + bit_num_); \ 20250397Sobrien CODE; \ 20350397Sobrien \ 20450397Sobrien if (word_ == 0) \ 20550397Sobrien break; \ 20650397Sobrien } \ 20750397Sobrien } \ 20850397Sobrien } \ 20950397Sobrien \ 21050397Sobrien bit_num_ = 0; \ 21150397Sobrien } \ 21250397Sobrien \ 21350397Sobrien word_num_ = 0; \ 21450397Sobrien } \ 21550397Sobrien} while (0) 21650397Sobrien 21750397Sobrien/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting 21850397Sobrien BITNUM to the bit number and executing CODE for all bits that are set in 21990075Sobrien the first bitmap and not set in the second. */ 22050397Sobrien 22150397Sobrien#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ 22250397Sobriendo { \ 22350397Sobrien bitmap_element *ptr1_ = (BITMAP1)->first; \ 22450397Sobrien bitmap_element *ptr2_ = (BITMAP2)->first; \ 22550397Sobrien unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 22650397Sobrien unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT); \ 22750397Sobrien unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT)) \ 22850397Sobrien % BITMAP_ELEMENT_WORDS); \ 22950397Sobrien \ 23050397Sobrien /* Find the block the minimum bit is in in the first bitmap. */ \ 23150397Sobrien while (ptr1_ != 0 && ptr1_->indx < indx_) \ 23250397Sobrien ptr1_ = ptr1_->next; \ 23350397Sobrien \ 23450397Sobrien if (ptr1_ != 0 && ptr1_->indx != indx_) \ 23550397Sobrien { \ 23650397Sobrien bit_num_ = 0; \ 23750397Sobrien word_num_ = 0; \ 23850397Sobrien } \ 23950397Sobrien \ 24050397Sobrien for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \ 24150397Sobrien { \ 24250397Sobrien /* Advance BITMAP2 to the equivalent link, using an all \ 24350397Sobrien zero element if an equivalent link doesn't exist. */ \ 24450397Sobrien bitmap_element *tmp2_; \ 24550397Sobrien \ 24650397Sobrien while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \ 24750397Sobrien ptr2_ = ptr2_->next; \ 24850397Sobrien \ 24950397Sobrien tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx) \ 25090075Sobrien ? ptr2_ : &bitmap_zero_bits); \ 25150397Sobrien \ 25250397Sobrien for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 25350397Sobrien { \ 25450397Sobrien unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_] \ 25550397Sobrien & ~ tmp2_->bits[word_num_]); \ 25650397Sobrien if (word_ != 0) \ 25750397Sobrien { \ 25850397Sobrien for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++) \ 25950397Sobrien { \ 26050397Sobrien unsigned HOST_WIDE_INT mask_ \ 26150397Sobrien = ((unsigned HOST_WIDE_INT)1) << bit_num_; \ 26250397Sobrien \ 26350397Sobrien if ((word_ & mask_) != 0) \ 26450397Sobrien { \ 26550397Sobrien word_ &= ~ mask_; \ 26650397Sobrien (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \ 26750397Sobrien + word_num_ * HOST_BITS_PER_WIDE_INT \ 26850397Sobrien + bit_num_); \ 26950397Sobrien \ 27050397Sobrien CODE; \ 27150397Sobrien if (word_ == 0) \ 27250397Sobrien break; \ 27350397Sobrien } \ 27450397Sobrien } \ 27550397Sobrien } \ 27650397Sobrien \ 27750397Sobrien bit_num_ = 0; \ 27850397Sobrien } \ 27950397Sobrien \ 28050397Sobrien word_num_ = 0; \ 28150397Sobrien } \ 28250397Sobrien} while (0) 28350397Sobrien 28450397Sobrien/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting 28550397Sobrien BITNUM to the bit number and executing CODE for all bits that are set in 28690075Sobrien the both bitmaps. */ 28750397Sobrien 28850397Sobrien#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ 28950397Sobriendo { \ 29050397Sobrien bitmap_element *ptr1_ = (BITMAP1)->first; \ 29150397Sobrien bitmap_element *ptr2_ = (BITMAP2)->first; \ 29250397Sobrien unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 29350397Sobrien unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT); \ 29450397Sobrien unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT)) \ 29550397Sobrien % BITMAP_ELEMENT_WORDS); \ 29650397Sobrien \ 29750397Sobrien /* Find the block the minimum bit is in in the first bitmap. */ \ 29850397Sobrien while (ptr1_ != 0 && ptr1_->indx < indx_) \ 29950397Sobrien ptr1_ = ptr1_->next; \ 30050397Sobrien \ 30150397Sobrien if (ptr1_ != 0 && ptr1_->indx != indx_) \ 30250397Sobrien { \ 30350397Sobrien bit_num_ = 0; \ 30450397Sobrien word_num_ = 0; \ 30550397Sobrien } \ 30650397Sobrien \ 30750397Sobrien for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \ 30850397Sobrien { \ 30950397Sobrien /* Advance BITMAP2 to the equivalent link */ \ 31050397Sobrien while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \ 31150397Sobrien ptr2_ = ptr2_->next; \ 31250397Sobrien \ 31350397Sobrien if (ptr2_ == 0) \ 31450397Sobrien { \ 31590075Sobrien /* If there are no more elements in BITMAP2, exit loop now. */ \ 31650397Sobrien ptr1_ = (bitmap_element *)0; \ 31750397Sobrien break; \ 31850397Sobrien } \ 31950397Sobrien else if (ptr2_->indx > ptr1_->indx) \ 32050397Sobrien { \ 32150397Sobrien bit_num_ = word_num_ = 0; \ 32250397Sobrien continue; \ 32350397Sobrien } \ 32450397Sobrien \ 32550397Sobrien for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 32650397Sobrien { \ 32750397Sobrien unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_] \ 32850397Sobrien & ptr2_->bits[word_num_]); \ 32950397Sobrien if (word_ != 0) \ 33050397Sobrien { \ 33150397Sobrien for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++) \ 33250397Sobrien { \ 33350397Sobrien unsigned HOST_WIDE_INT mask_ \ 33450397Sobrien = ((unsigned HOST_WIDE_INT)1) << bit_num_; \ 33550397Sobrien \ 33650397Sobrien if ((word_ & mask_) != 0) \ 33750397Sobrien { \ 33850397Sobrien word_ &= ~ mask_; \ 33950397Sobrien (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \ 34050397Sobrien + word_num_ * HOST_BITS_PER_WIDE_INT \ 34150397Sobrien + bit_num_); \ 34250397Sobrien \ 34350397Sobrien CODE; \ 34450397Sobrien if (word_ == 0) \ 34550397Sobrien break; \ 34650397Sobrien } \ 34750397Sobrien } \ 34850397Sobrien } \ 34950397Sobrien \ 35050397Sobrien bit_num_ = 0; \ 35150397Sobrien } \ 35250397Sobrien \ 35350397Sobrien word_num_ = 0; \ 35450397Sobrien } \ 35550397Sobrien} while (0) 35690075Sobrien 35790075Sobrien#endif /* GCC_BITMAP_H */ 358