sbitmap.h revision 169689
1/* Simple bitmaps. 2 Copyright (C) 1999, 2000, 2002, 2003, 2004 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 2, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 1902110-1301, USA. */ 20 21#ifndef GCC_SBITMAP_H 22#define GCC_SBITMAP_H 23 24/* It's not clear yet whether using bitmap.[ch] will be a win. 25 It should be straightforward to convert so for now we keep things simple 26 while more important issues are dealt with. */ 27 28#define SBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT) 29#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT 30 31typedef struct simple_bitmap_def 32{ 33 unsigned int n_bits; /* Number of bits. */ 34 unsigned int size; /* Size in elements. */ 35 unsigned int bytes; /* Size in bytes. */ 36 SBITMAP_ELT_TYPE elms[1]; /* The elements. */ 37} *sbitmap; 38 39typedef SBITMAP_ELT_TYPE *sbitmap_ptr; 40 41/* Return the set size needed for N elements. */ 42#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS) 43 44/* Set bit number bitno in the bitmap. */ 45#define SET_BIT(BITMAP, BITNO) \ 46 ((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] \ 47 |= (SBITMAP_ELT_TYPE) 1 << (BITNO) % SBITMAP_ELT_BITS) 48 49/* Test if bit number bitno in the bitmap is set. */ 50#define TEST_BIT(BITMAP, BITNO) \ 51((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] >> (BITNO) % SBITMAP_ELT_BITS & 1) 52 53/* Reset bit number bitno in the bitmap. */ 54#define RESET_BIT(BITMAP, BITNO) \ 55 ((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] \ 56 &= ~((SBITMAP_ELT_TYPE) 1 << (BITNO) % SBITMAP_ELT_BITS)) 57 58/* The iterator for sbitmap. */ 59typedef struct { 60 /* The pointer to the first word of the bitmap. */ 61 SBITMAP_ELT_TYPE *ptr; 62 63 /* The size of the bitmap. */ 64 unsigned int size; 65 66 /* The current word index. */ 67 unsigned int word_num; 68 69 /* The current bit index (not modulo SBITMAP_ELT_BITS). */ 70 unsigned int bit_num; 71 72 /* The words currently visited. */ 73 SBITMAP_ELT_TYPE word; 74} sbitmap_iterator; 75 76/* Initialize the iterator I with sbitmap BMP and the initial index 77 MIN. */ 78 79static inline void 80sbitmap_iter_init (sbitmap_iterator *i, sbitmap bmp, unsigned int min) 81{ 82 i->word_num = min / (unsigned int) SBITMAP_ELT_BITS; 83 i->bit_num = min; 84 i->size = bmp->size; 85 i->ptr = bmp->elms; 86 87 if (i->word_num >= i->size) 88 i->word = 0; 89 else 90 i->word = (i->ptr[i->word_num] 91 >> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS)); 92} 93 94/* Return true if we have more bits to visit, in which case *N is set 95 to the index of the bit to be visited. Otherwise, return 96 false. */ 97 98static inline bool 99sbitmap_iter_cond (sbitmap_iterator *i, unsigned int *n) 100{ 101 /* Skip words that are zeros. */ 102 for (; i->word == 0; i->word = i->ptr[i->word_num]) 103 { 104 i->word_num++; 105 106 /* If we have reached the end, break. */ 107 if (i->word_num >= i->size) 108 return false; 109 110 i->bit_num = i->word_num * SBITMAP_ELT_BITS; 111 } 112 113 /* Skip bits that are zero. */ 114 for (; (i->word & 1) == 0; i->word >>= 1) 115 i->bit_num++; 116 117 *n = i->bit_num; 118 119 return true; 120} 121 122/* Advance to the next bit. */ 123 124static inline void 125sbitmap_iter_next (sbitmap_iterator *i) 126{ 127 i->word >>= 1; 128 i->bit_num++; 129} 130 131/* Loop over all elements of SBITMAP, starting with MIN. In each 132 iteration, N is set to the index of the bit being visited. ITER is 133 an instance of sbitmap_iterator used to iterate the bitmap. */ 134 135#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, ITER) \ 136 for (sbitmap_iter_init (&(ITER), (SBITMAP), (MIN)); \ 137 sbitmap_iter_cond (&(ITER), &(N)); \ 138 sbitmap_iter_next (&(ITER))) 139 140#define EXECUTE_IF_SET_IN_SBITMAP_REV(SBITMAP, N, CODE) \ 141do { \ 142 unsigned int word_num_; \ 143 unsigned int bit_num_; \ 144 unsigned int size_ = (SBITMAP)->size; \ 145 SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \ 146 \ 147 for (word_num_ = size_; word_num_ > 0; word_num_--) \ 148 { \ 149 SBITMAP_ELT_TYPE word_ = ptr_[word_num_ - 1]; \ 150 \ 151 if (word_ != 0) \ 152 for (bit_num_ = SBITMAP_ELT_BITS; bit_num_ > 0; bit_num_--) \ 153 { \ 154 SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE)1 << (bit_num_ - 1);\ 155 \ 156 if ((word_ & _mask) != 0) \ 157 { \ 158 word_ &= ~ _mask; \ 159 (N) = (word_num_ - 1) * SBITMAP_ELT_BITS + bit_num_ - 1;\ 160 CODE; \ 161 if (word_ == 0) \ 162 break; \ 163 } \ 164 } \ 165 } \ 166} while (0) 167 168#define sbitmap_free(MAP) free(MAP) 169#define sbitmap_vector_free(VEC) free(VEC) 170 171struct int_list; 172 173extern void dump_sbitmap (FILE *, sbitmap); 174extern void dump_sbitmap_file (FILE *, sbitmap); 175extern void dump_sbitmap_vector (FILE *, const char *, const char *, sbitmap *, 176 int); 177extern sbitmap sbitmap_alloc (unsigned int); 178extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int); 179extern sbitmap sbitmap_resize (sbitmap, unsigned int, int); 180extern void sbitmap_copy (sbitmap, sbitmap); 181extern int sbitmap_equal (sbitmap, sbitmap); 182extern void sbitmap_zero (sbitmap); 183extern void sbitmap_ones (sbitmap); 184extern void sbitmap_vector_zero (sbitmap *, unsigned int); 185extern void sbitmap_vector_ones (sbitmap *, unsigned int); 186 187extern void sbitmap_union_of_diff (sbitmap, sbitmap, sbitmap, sbitmap); 188extern bool sbitmap_union_of_diff_cg (sbitmap, sbitmap, sbitmap, sbitmap); 189extern void sbitmap_difference (sbitmap, sbitmap, sbitmap); 190extern void sbitmap_not (sbitmap, sbitmap); 191extern void sbitmap_a_or_b_and_c (sbitmap, sbitmap, sbitmap, sbitmap); 192extern bool sbitmap_a_or_b_and_c_cg (sbitmap, sbitmap, sbitmap, sbitmap); 193extern void sbitmap_a_and_b_or_c (sbitmap, sbitmap, sbitmap, sbitmap); 194extern bool sbitmap_a_and_b_or_c_cg (sbitmap, sbitmap, sbitmap, sbitmap); 195extern bool sbitmap_any_common_bits (sbitmap, sbitmap); 196extern void sbitmap_a_and_b (sbitmap, sbitmap, sbitmap); 197extern bool sbitmap_a_and_b_cg (sbitmap, sbitmap, sbitmap); 198extern void sbitmap_a_or_b (sbitmap, sbitmap, sbitmap); 199extern bool sbitmap_a_or_b_cg (sbitmap, sbitmap, sbitmap); 200extern void sbitmap_a_xor_b (sbitmap, sbitmap, sbitmap); 201extern bool sbitmap_a_xor_b_cg (sbitmap, sbitmap, sbitmap); 202extern bool sbitmap_a_subset_b_p (sbitmap, sbitmap); 203 204extern int sbitmap_first_set_bit (sbitmap); 205extern int sbitmap_last_set_bit (sbitmap); 206 207extern void sbitmap_intersect_of_predsucc (sbitmap, sbitmap *, int, 208 struct int_list **); 209#define sbitmap_intersect_of_predecessors sbitmap_intersect_of_predsucc 210#define sbitmap_intersect_of_successors sbitmap_intersect_of_predsucc 211 212extern void sbitmap_union_of_predsucc (sbitmap, sbitmap *, int, 213 struct int_list **); 214#define sbitmap_union_of_predecessors sbitmap_union_of_predsucc 215#define sbitmap_union_of_successors sbitmap_union_of_predsucc 216 217/* Intersection and Union of preds/succs using the new flow graph 218 structure instead of the pred/succ arrays. */ 219 220extern void sbitmap_intersection_of_succs (sbitmap, sbitmap *, int); 221extern void sbitmap_intersection_of_preds (sbitmap, sbitmap *, int); 222extern void sbitmap_union_of_succs (sbitmap, sbitmap *, int); 223extern void sbitmap_union_of_preds (sbitmap, sbitmap *, int); 224 225extern void debug_sbitmap (sbitmap); 226extern sbitmap sbitmap_realloc (sbitmap, unsigned int); 227#endif /* ! GCC_SBITMAP_H */ 228