OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.2.2/] [gcc/] [bitmap.h] - Blame information for rev 193

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.