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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [bitmap.c] - Blame information for rev 827

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, 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
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "rtl.h"
26
#include "flags.h"
27
#include "obstack.h"
28
#include "ggc.h"
29
#include "bitmap.h"
30
 
31
/* Global data */
32
bitmap_element bitmap_zero_bits;  /* An element of all zero bits.  */
33
bitmap_obstack bitmap_default_obstack;    /* The default bitmap obstack.  */
34
static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
35
                                                            GC'd elements.  */
36
 
37
static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
38
static void bitmap_element_free (bitmap, bitmap_element *);
39
static bitmap_element *bitmap_element_allocate (bitmap);
40
static int bitmap_element_zerop (bitmap_element *);
41
static void bitmap_element_link (bitmap, bitmap_element *);
42
static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);
43
static void bitmap_elt_clear_from (bitmap, bitmap_element *);
44
static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
45
 
46
 
47
/* Add ELEM to the appropriate freelist.  */
48
static inline void
49
bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
50
{
51
  bitmap_obstack *bit_obstack = head->obstack;
52
 
53
  elt->next = NULL;
54
  if (bit_obstack)
55
    {
56
      elt->prev = bit_obstack->elements;
57
      bit_obstack->elements = elt;
58
    }
59
  else
60
    {
61
      elt->prev = bitmap_ggc_free;
62
      bitmap_ggc_free = elt;
63
    }
64
}
65
 
66
/* Free a bitmap element.  Since these are allocated off the
67
   bitmap_obstack, "free" actually means "put onto the freelist".  */
68
 
69
static inline void
70
bitmap_element_free (bitmap head, bitmap_element *elt)
71
{
72
  bitmap_element *next = elt->next;
73
  bitmap_element *prev = elt->prev;
74
 
75
  if (prev)
76
    prev->next = next;
77
 
78
  if (next)
79
    next->prev = prev;
80
 
81
  if (head->first == elt)
82
    head->first = next;
83
 
84
  /* Since the first thing we try is to insert before current,
85
     make current the next entry in preference to the previous.  */
86
  if (head->current == elt)
87
    {
88
      head->current = next != 0 ? next : prev;
89
      if (head->current)
90
        head->indx = head->current->indx;
91
      else
92
        head->indx = 0;
93
    }
94
  bitmap_elem_to_freelist (head, elt);
95
}
96
 
97
/* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
98
 
99
static inline bitmap_element *
100
bitmap_element_allocate (bitmap head)
101
{
102
  bitmap_element *element;
103
  bitmap_obstack *bit_obstack = head->obstack;
104
 
105
  if (bit_obstack)
106
    {
107
      element = bit_obstack->elements;
108
 
109
      if (element)
110
        /* Use up the inner list first before looking at the next
111
           element of the outer list.  */
112
        if (element->next)
113
          {
114
            bit_obstack->elements = element->next;
115
            bit_obstack->elements->prev = element->prev;
116
          }
117
        else
118
          /*  Inner list was just a singleton.  */
119
          bit_obstack->elements = element->prev;
120
      else
121
        element = XOBNEW (&bit_obstack->obstack, bitmap_element);
122
    }
123
  else
124
    {
125
      element = bitmap_ggc_free;
126
      if (element)
127
        /* Use up the inner list first before looking at the next
128
           element of the outer list.  */
129
        if (element->next)
130
          {
131
            bitmap_ggc_free = element->next;
132
            bitmap_ggc_free->prev = element->prev;
133
          }
134
        else
135
          /*  Inner list was just a singleton.  */
136
          bitmap_ggc_free = element->prev;
137
      else
138
        element = GGC_NEW (bitmap_element);
139
    }
140
 
141
  memset (element->bits, 0, sizeof (element->bits));
142
 
143
  return element;
144
}
145
 
146
/* Remove ELT and all following elements from bitmap HEAD.  */
147
 
148
void
149
bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
150
{
151
  bitmap_element *prev;
152
  bitmap_obstack *bit_obstack = head->obstack;
153
 
154
  if (!elt) return;
155
 
156
  prev = elt->prev;
157
  if (prev)
158
    {
159
      prev->next = NULL;
160
      if (head->current->indx > prev->indx)
161
        {
162
          head->current = prev;
163
          head->indx = prev->indx;
164
        }
165
    }
166
  else
167
    {
168
      head->first = NULL;
169
      head->current = NULL;
170
      head->indx = 0;
171
    }
172
 
173
  /* Put the entire list onto the free list in one operation. */
174
  if (bit_obstack)
175
    {
176
      elt->prev = bit_obstack->elements;
177
      bit_obstack->elements = elt;
178
    }
179
  else
180
    {
181
      elt->prev = bitmap_ggc_free;
182
      bitmap_ggc_free = elt;
183
    }
184
}
185
 
186
/* Clear a bitmap by freeing the linked list.  */
187
 
188
inline void
189
bitmap_clear (bitmap head)
190
{
191
  if (head->first)
192
    bitmap_elt_clear_from (head, head->first);
193
}
194
 
195
/* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
196
   the default bitmap obstack.  */
197
 
198
void
199
bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
200
{
201
  if (!bit_obstack)
202
    bit_obstack = &bitmap_default_obstack;
203
 
204
#if !defined(__GNUC__) || (__GNUC__ < 2)
205
#define __alignof__(type) 0
206
#endif
207
 
208
  bit_obstack->elements = NULL;
209
  bit_obstack->heads = NULL;
210
  obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
211
                              __alignof__ (bitmap_element),
212
                              obstack_chunk_alloc,
213
                              obstack_chunk_free);
214
}
215
 
216
/* Release the memory from a bitmap obstack.  If BIT_OBSTACK is NULL,
217
   release the default bitmap obstack.  */
218
 
219
void
220
bitmap_obstack_release (bitmap_obstack *bit_obstack)
221
{
222
  if (!bit_obstack)
223
    bit_obstack = &bitmap_default_obstack;
224
 
225
  bit_obstack->elements = NULL;
226
  bit_obstack->heads = NULL;
227
  obstack_free (&bit_obstack->obstack, NULL);
228
}
229
 
230
/* Create a new bitmap on an obstack.  If BIT_OBSTACK is NULL, create
231
   it on the default bitmap obstack.  */
232
 
233
bitmap
234
bitmap_obstack_alloc (bitmap_obstack *bit_obstack)
235
{
236
  bitmap map;
237
 
238
  if (!bit_obstack)
239
    bit_obstack = &bitmap_default_obstack;
240
  map = bit_obstack->heads;
241
  if (map)
242
    bit_obstack->heads = (void *)map->first;
243
  else
244
    map = XOBNEW (&bit_obstack->obstack, bitmap_head);
245
  bitmap_initialize (map, bit_obstack);
246
 
247
  return map;
248
}
249
 
250
/* Create a new GCd bitmap.  */
251
 
252
bitmap
253
bitmap_gc_alloc (void)
254
{
255
  bitmap map;
256
 
257
  map = GGC_NEW (struct bitmap_head_def);
258
  bitmap_initialize (map, NULL);
259
 
260
  return map;
261
}
262
 
263
/* Release an obstack allocated bitmap.  */
264
 
265
void
266
bitmap_obstack_free (bitmap map)
267
{
268
  if (map)
269
    {
270
      bitmap_clear (map);
271
      map->first = (void *)map->obstack->heads;
272
      map->obstack->heads = map;
273
    }
274
}
275
 
276
 
277
/* Return nonzero if all bits in an element are zero.  */
278
 
279
static inline int
280
bitmap_element_zerop (bitmap_element *element)
281
{
282
#if BITMAP_ELEMENT_WORDS == 2
283
  return (element->bits[0] | element->bits[1]) == 0;
284
#else
285
  unsigned i;
286
 
287
  for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
288
    if (element->bits[i] != 0)
289
      return 0;
290
 
291
  return 1;
292
#endif
293
}
294
 
295
/* Link the bitmap element into the current bitmap linked list.  */
296
 
297
static inline void
298
bitmap_element_link (bitmap head, bitmap_element *element)
299
{
300
  unsigned int indx = element->indx;
301
  bitmap_element *ptr;
302
 
303
  /* If this is the first and only element, set it in.  */
304
  if (head->first == 0)
305
    {
306
      element->next = element->prev = 0;
307
      head->first = element;
308
    }
309
 
310
  /* If this index is less than that of the current element, it goes someplace
311
     before the current element.  */
312
  else if (indx < head->indx)
313
    {
314
      for (ptr = head->current;
315
           ptr->prev != 0 && ptr->prev->indx > indx;
316
           ptr = ptr->prev)
317
        ;
318
 
319
      if (ptr->prev)
320
        ptr->prev->next = element;
321
      else
322
        head->first = element;
323
 
324
      element->prev = ptr->prev;
325
      element->next = ptr;
326
      ptr->prev = element;
327
    }
328
 
329
  /* Otherwise, it must go someplace after the current element.  */
330
  else
331
    {
332
      for (ptr = head->current;
333
           ptr->next != 0 && ptr->next->indx < indx;
334
           ptr = ptr->next)
335
        ;
336
 
337
      if (ptr->next)
338
        ptr->next->prev = element;
339
 
340
      element->next = ptr->next;
341
      element->prev = ptr;
342
      ptr->next = element;
343
    }
344
 
345
  /* Set up so this is the first element searched.  */
346
  head->current = element;
347
  head->indx = indx;
348
}
349
 
350
/* Insert a new uninitialized element into bitmap HEAD after element
351
   ELT.  If ELT is NULL, insert the element at the start.  Return the
352
   new element.  */
353
 
354
static bitmap_element *
355
bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
356
{
357
  bitmap_element *node = bitmap_element_allocate (head);
358
  node->indx = indx;
359
 
360
  if (!elt)
361
    {
362
      if (!head->current)
363
        {
364
          head->current = node;
365
          head->indx = indx;
366
        }
367
      node->next = head->first;
368
      if (node->next)
369
        node->next->prev = node;
370
      head->first = node;
371
      node->prev = NULL;
372
    }
373
  else
374
    {
375
      gcc_assert (head->current);
376
      node->next = elt->next;
377
      if (node->next)
378
        node->next->prev = node;
379
      elt->next = node;
380
      node->prev = elt;
381
    }
382
  return node;
383
}
384
 
385
/* Copy a bitmap to another bitmap.  */
386
 
387
void
388
bitmap_copy (bitmap to, bitmap from)
389
{
390
  bitmap_element *from_ptr, *to_ptr = 0;
391
 
392
  bitmap_clear (to);
393
 
394
  /* Copy elements in forward direction one at a time.  */
395
  for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
396
    {
397
      bitmap_element *to_elt = bitmap_element_allocate (to);
398
 
399
      to_elt->indx = from_ptr->indx;
400
      memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
401
 
402
      /* Here we have a special case of bitmap_element_link, for the case
403
         where we know the links are being entered in sequence.  */
404
      if (to_ptr == 0)
405
        {
406
          to->first = to->current = to_elt;
407
          to->indx = from_ptr->indx;
408
          to_elt->next = to_elt->prev = 0;
409
        }
410
      else
411
        {
412
          to_elt->prev = to_ptr;
413
          to_elt->next = 0;
414
          to_ptr->next = to_elt;
415
        }
416
 
417
      to_ptr = to_elt;
418
    }
419
}
420
 
421
/* Find a bitmap element that would hold a bitmap's bit.
422
   Update the `current' field even if we can't find an element that
423
   would hold the bitmap's bit to make eventual allocation
424
   faster.  */
425
 
426
static inline bitmap_element *
427
bitmap_find_bit (bitmap head, unsigned int bit)
428
{
429
  bitmap_element *element;
430
  unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
431
 
432
  if (head->current == 0
433
      || head->indx == indx)
434
    return head->current;
435
 
436
  if (head->indx < indx)
437
    /* INDX is beyond head->indx.  Search from head->current
438
       forward.  */
439
    for (element = head->current;
440
         element->next != 0 && element->indx < indx;
441
         element = element->next)
442
      ;
443
 
444
  else if (head->indx / 2 < indx)
445
    /* INDX is less than head->indx and closer to head->indx than to
446
       0.  Search from head->current backward.  */
447
    for (element = head->current;
448
         element->prev != 0 && element->indx > indx;
449
         element = element->prev)
450
      ;
451
 
452
  else
453
    /* INDX is less than head->indx and closer to 0 than to
454
       head->indx.  Search from head->first forward.  */
455
    for (element = head->first;
456
         element->next != 0 && element->indx < indx;
457
         element = element->next)
458
      ;
459
 
460
  /* `element' is the nearest to the one we want.  If it's not the one we
461
     want, the one we want doesn't exist.  */
462
  head->current = element;
463
  head->indx = element->indx;
464
  if (element != 0 && element->indx != indx)
465
    element = 0;
466
 
467
  return element;
468
}
469
 
470
/* Clear a single bit in a bitmap.  */
471
 
472
void
473
bitmap_clear_bit (bitmap head, int bit)
474
{
475
  bitmap_element *ptr = bitmap_find_bit (head, bit);
476
 
477
  if (ptr != 0)
478
    {
479
      unsigned bit_num  = bit % BITMAP_WORD_BITS;
480
      unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
481
      ptr->bits[word_num] &= ~ (((BITMAP_WORD) 1) << bit_num);
482
 
483
      /* If we cleared the entire word, free up the element.  */
484
      if (bitmap_element_zerop (ptr))
485
        bitmap_element_free (head, ptr);
486
    }
487
}
488
 
489
/* Set a single bit in a bitmap.  */
490
 
491
void
492
bitmap_set_bit (bitmap head, int bit)
493
{
494
  bitmap_element *ptr = bitmap_find_bit (head, bit);
495
  unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
496
  unsigned bit_num  = bit % BITMAP_WORD_BITS;
497
  BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
498
 
499
  if (ptr == 0)
500
    {
501
      ptr = bitmap_element_allocate (head);
502
      ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
503
      ptr->bits[word_num] = bit_val;
504
      bitmap_element_link (head, ptr);
505
    }
506
  else
507
    ptr->bits[word_num] |= bit_val;
508
}
509
 
510
/* Return whether a bit is set within a bitmap.  */
511
 
512
int
513
bitmap_bit_p (bitmap head, int bit)
514
{
515
  bitmap_element *ptr;
516
  unsigned bit_num;
517
  unsigned word_num;
518
 
519
  ptr = bitmap_find_bit (head, bit);
520
  if (ptr == 0)
521
    return 0;
522
 
523
  bit_num = bit % BITMAP_WORD_BITS;
524
  word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
525
 
526
  return (ptr->bits[word_num] >> bit_num) & 1;
527
}
528
 
529
#if GCC_VERSION < 3400
530
/* Table of number of set bits in a character, indexed by value of char.  */
531
static unsigned char popcount_table[] =
532
{
533
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
534
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
535
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
536
    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
537
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
538
    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
539
    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
540
    3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
541
};
542
 
543
static unsigned long
544
bitmap_popcount (BITMAP_WORD a)
545
{
546
  unsigned long ret = 0;
547
  unsigned i;
548
 
549
  /* Just do this the table way for now  */
550
  for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
551
    ret += popcount_table[(a >> i) & 0xff];
552
  return ret;
553
}
554
#endif
555
/* Count the number of bits set in the bitmap, and return it.  */
556
 
557
unsigned long
558
bitmap_count_bits (bitmap a)
559
{
560
  unsigned long count = 0;
561
  bitmap_element *elt;
562
  unsigned ix;
563
 
564
  for (elt = a->first; elt; elt = elt->next)
565
    {
566
      for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
567
        {
568
#if GCC_VERSION >= 3400
569
          /* Note that popcountl matches BITMAP_WORD in type, so the actual size
570
         of BITMAP_WORD is not material.  */
571
          count += __builtin_popcountl (elt->bits[ix]);
572
#else
573
          count += bitmap_popcount (elt->bits[ix]);
574
#endif
575
        }
576
    }
577
  return count;
578
}
579
 
580
 
581
 
582
/* Return the bit number of the first set bit in the bitmap.  The
583
   bitmap must be non-empty.  */
584
 
585
unsigned
586
bitmap_first_set_bit (bitmap a)
587
{
588
  bitmap_element *elt = a->first;
589
  unsigned bit_no;
590
  BITMAP_WORD word;
591
  unsigned ix;
592
 
593
  gcc_assert (elt);
594
  bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
595
  for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
596
    {
597
      word = elt->bits[ix];
598
      if (word)
599
        goto found_bit;
600
    }
601
  gcc_unreachable ();
602
 found_bit:
603
  bit_no += ix * BITMAP_WORD_BITS;
604
 
605
#if GCC_VERSION >= 3004
606
  gcc_assert (sizeof(long) == sizeof (word));
607
  bit_no += __builtin_ctzl (word);
608
#else
609
  /* Binary search for the first set bit.  */
610
#if BITMAP_WORD_BITS > 64
611
#error "Fill out the table."
612
#endif
613
#if BITMAP_WORD_BITS > 32
614
  if (!(word & 0xffffffff))
615
    word >>= 32, bit_no += 32;
616
#endif
617
  if (!(word & 0xffff))
618
    word >>= 16, bit_no += 16;
619
  if (!(word & 0xff))
620
    word >>= 8, bit_no += 8;
621
  if (!(word & 0xf))
622
    word >>= 4, bit_no += 4;
623
  if (!(word & 0x3))
624
    word >>= 2, bit_no += 2;
625
  if (!(word & 0x1))
626
    word >>= 1, bit_no += 1;
627
 
628
 gcc_assert (word & 1);
629
#endif
630
 return bit_no;
631
}
632
 
633
 
634
/* DST = A & B.  */
635
 
636
void
637
bitmap_and (bitmap dst, bitmap a, bitmap b)
638
{
639
  bitmap_element *dst_elt = dst->first;
640
  bitmap_element *a_elt = a->first;
641
  bitmap_element *b_elt = b->first;
642
  bitmap_element *dst_prev = NULL;
643
 
644
  gcc_assert (dst != a && dst != b);
645
 
646
  if (a == b)
647
    {
648
      bitmap_copy (dst, a);
649
      return;
650
    }
651
 
652
  while (a_elt && b_elt)
653
    {
654
      if (a_elt->indx < b_elt->indx)
655
        a_elt = a_elt->next;
656
      else if (b_elt->indx < a_elt->indx)
657
        b_elt = b_elt->next;
658
      else
659
        {
660
          /* Matching elts, generate A & B.  */
661
          unsigned ix;
662
          BITMAP_WORD ior = 0;
663
 
664
          if (!dst_elt)
665
            dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
666
          else
667
            dst_elt->indx = a_elt->indx;
668
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
669
            {
670
              BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
671
 
672
              dst_elt->bits[ix] = r;
673
              ior |= r;
674
            }
675
          if (ior)
676
            {
677
              dst_prev = dst_elt;
678
              dst_elt = dst_elt->next;
679
            }
680
          a_elt = a_elt->next;
681
          b_elt = b_elt->next;
682
        }
683
    }
684
  bitmap_elt_clear_from (dst, dst_elt);
685
  gcc_assert (!dst->current == !dst->first);
686
  if (dst->current)
687
    dst->indx = dst->current->indx;
688
}
689
 
690
/* A &= B.  */
691
 
692
void
693
bitmap_and_into (bitmap a, bitmap b)
694
{
695
  bitmap_element *a_elt = a->first;
696
  bitmap_element *b_elt = b->first;
697
  bitmap_element *next;
698
 
699
  if (a == b)
700
    return;
701
 
702
  while (a_elt && b_elt)
703
    {
704
      if (a_elt->indx < b_elt->indx)
705
        {
706
          next = a_elt->next;
707
          bitmap_element_free (a, a_elt);
708
          a_elt = next;
709
        }
710
      else if (b_elt->indx < a_elt->indx)
711
        b_elt = b_elt->next;
712
      else
713
        {
714
          /* Matching elts, generate A &= B.  */
715
          unsigned ix;
716
          BITMAP_WORD ior = 0;
717
 
718
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
719
            {
720
              BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
721
 
722
              a_elt->bits[ix] = r;
723
              ior |= r;
724
            }
725
          next = a_elt->next;
726
          if (!ior)
727
            bitmap_element_free (a, a_elt);
728
          a_elt = next;
729
          b_elt = b_elt->next;
730
        }
731
    }
732
  bitmap_elt_clear_from (a, a_elt);
733
  gcc_assert (!a->current == !a->first);
734
  gcc_assert (!a->current || a->indx == a->current->indx);
735
}
736
 
737
/* DST = A & ~B  */
738
 
739
void
740
bitmap_and_compl (bitmap dst, bitmap a, bitmap b)
741
{
742
  bitmap_element *dst_elt = dst->first;
743
  bitmap_element *a_elt = a->first;
744
  bitmap_element *b_elt = b->first;
745
  bitmap_element *dst_prev = NULL;
746
 
747
  gcc_assert (dst != a && dst != b);
748
 
749
  if (a == b)
750
    {
751
      bitmap_clear (dst);
752
      return;
753
    }
754
 
755
  while (a_elt)
756
    {
757
      if (!b_elt || a_elt->indx < b_elt->indx)
758
        {
759
          /* Copy a_elt.  */
760
          if (!dst_elt)
761
            dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
762
          else
763
            dst_elt->indx = a_elt->indx;
764
          memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits));
765
          dst_prev = dst_elt;
766
          dst_elt = dst_elt->next;
767
          a_elt = a_elt->next;
768
        }
769
      else if (b_elt->indx < a_elt->indx)
770
        b_elt = b_elt->next;
771
      else
772
        {
773
          /* Matching elts, generate A & ~B.  */
774
          unsigned ix;
775
          BITMAP_WORD ior = 0;
776
 
777
          if (!dst_elt)
778
            dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
779
          else
780
            dst_elt->indx = a_elt->indx;
781
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
782
            {
783
              BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
784
 
785
              dst_elt->bits[ix] = r;
786
              ior |= r;
787
            }
788
          if (ior)
789
            {
790
              dst_prev = dst_elt;
791
              dst_elt = dst_elt->next;
792
            }
793
          a_elt = a_elt->next;
794
          b_elt = b_elt->next;
795
        }
796
    }
797
  bitmap_elt_clear_from (dst, dst_elt);
798
  gcc_assert (!dst->current == !dst->first);
799
  if (dst->current)
800
    dst->indx = dst->current->indx;
801
}
802
 
803
/* A &= ~B. Returns true if A changes */
804
 
805
bool
806
bitmap_and_compl_into (bitmap a, bitmap b)
807
{
808
  bitmap_element *a_elt = a->first;
809
  bitmap_element *b_elt = b->first;
810
  bitmap_element *next;
811
  BITMAP_WORD changed = 0;
812
 
813
  if (a == b)
814
    {
815
      if (bitmap_empty_p (a))
816
        return false;
817
      else
818
        {
819
          bitmap_clear (a);
820
          return true;
821
        }
822
    }
823
 
824
  while (a_elt && b_elt)
825
    {
826
      if (a_elt->indx < b_elt->indx)
827
        a_elt = a_elt->next;
828
      else if (b_elt->indx < a_elt->indx)
829
        b_elt = b_elt->next;
830
      else
831
        {
832
          /* Matching elts, generate A &= ~B.  */
833
          unsigned ix;
834
          BITMAP_WORD ior = 0;
835
 
836
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
837
            {
838
              BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
839
              BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
840
 
841
              a_elt->bits[ix] = r;
842
              changed |= cleared;
843
              ior |= r;
844
            }
845
          next = a_elt->next;
846
          if (!ior)
847
            bitmap_element_free (a, a_elt);
848
          a_elt = next;
849
          b_elt = b_elt->next;
850
        }
851
    }
852
  gcc_assert (!a->current == !a->first);
853
  gcc_assert (!a->current || a->indx == a->current->indx);
854
  return changed != 0;
855
}
856
 
857
/* Clear COUNT bits from START in HEAD.  */
858
void
859
bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
860
{
861
  unsigned int first_index = start / BITMAP_ELEMENT_ALL_BITS;
862
  unsigned int end_bit_plus1 = start + count;
863
  unsigned int end_bit = end_bit_plus1 - 1;
864
  unsigned int last_index = (end_bit) / BITMAP_ELEMENT_ALL_BITS;
865
  bitmap_element *elt = bitmap_find_bit (head, start);
866
 
867
  /* If bitmap_find_bit returns zero, the current is the closest block
868
     to the result.  If the current is less than first index, find the
869
     next one.  Otherwise, just set elt to be current.  */
870
  if (!elt)
871
    {
872
      if (head->current)
873
        {
874
          if (head->indx < first_index)
875
            {
876
              elt = head->current->next;
877
              if (!elt)
878
                return;
879
            }
880
          else
881
            elt = head->current;
882
        }
883
      else
884
        return;
885
    }
886
 
887
  while (elt && (elt->indx <= last_index))
888
    {
889
      bitmap_element * next_elt = elt->next;
890
      unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
891
      unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
892
 
893
 
894
      if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
895
        /* Get rid of the entire elt and go to the next one.  */
896
        bitmap_element_free (head, elt);
897
      else
898
        {
899
          /* Going to have to knock out some bits in this elt.  */
900
          unsigned int first_word_to_mod;
901
          BITMAP_WORD first_mask;
902
          unsigned int last_word_to_mod;
903
          BITMAP_WORD last_mask;
904
          unsigned int i;
905
          bool clear = true;
906
 
907
          if (elt_start_bit <= start)
908
            {
909
              /* The first bit to turn off is somewhere inside this
910
                 elt.  */
911
              first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
912
 
913
              /* This mask should have 1s in all bits >= start position. */
914
              first_mask =
915
                (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
916
              first_mask = ~first_mask;
917
            }
918
          else
919
            {
920
              /* The first bit to turn off is below this start of this elt.  */
921
              first_word_to_mod = 0;
922
              first_mask = 0;
923
              first_mask = ~first_mask;
924
            }
925
 
926
          if (elt_end_bit_plus1 <= end_bit_plus1)
927
            {
928
              /* The last bit to turn off is beyond this elt.  */
929
              last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
930
              last_mask = 0;
931
              last_mask = ~last_mask;
932
            }
933
          else
934
            {
935
              /* The last bit to turn off is inside to this elt.  */
936
              last_word_to_mod =
937
                (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
938
 
939
              /* The last mask should have 1s below the end bit.  */
940
              last_mask =
941
                (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
942
            }
943
 
944
 
945
          if (first_word_to_mod == last_word_to_mod)
946
            {
947
              BITMAP_WORD mask = first_mask & last_mask;
948
              elt->bits[first_word_to_mod] &= ~mask;
949
            }
950
          else
951
            {
952
              elt->bits[first_word_to_mod] &= ~first_mask;
953
              for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
954
                elt->bits[i] = 0;
955
              elt->bits[last_word_to_mod] &= ~last_mask;
956
            }
957
          for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
958
            if (elt->bits[i])
959
              {
960
                clear = false;
961
                break;
962
              }
963
          /* Check to see if there are any bits left.  */
964
          if (clear)
965
            bitmap_element_free (head, elt);
966
        }
967
      elt = next_elt;
968
    }
969
 
970
  if (elt)
971
    {
972
      head->current = elt;
973
      head->indx = head->current->indx;
974
    }
975
}
976
 
977
/* A = ~A & B. */
978
 
979
void
980
bitmap_compl_and_into (bitmap a, bitmap b)
981
{
982
  bitmap_element *a_elt = a->first;
983
  bitmap_element *b_elt = b->first;
984
  bitmap_element *a_prev = NULL;
985
  bitmap_element *next;
986
 
987
  gcc_assert (a != b);
988
 
989
  if (bitmap_empty_p (a))
990
    {
991
      bitmap_copy (a, b);
992
      return;
993
    }
994
  if (bitmap_empty_p (b))
995
    {
996
      bitmap_clear (a);
997
      return;
998
    }
999
 
1000
  while (a_elt || b_elt)
1001
    {
1002
      if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1003
        {
1004
          /* A is before B.  Remove A */
1005
          next = a_elt->next;
1006
          a_prev = a_elt->prev;
1007
          bitmap_element_free (a, a_elt);
1008
          a_elt = next;
1009
        }
1010
      else if (!a_elt || b_elt->indx < a_elt->indx)
1011
        {
1012
          /* B is before A.  Copy B. */
1013
          next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1014
          memcpy (next->bits, b_elt->bits, sizeof (next->bits));
1015
          a_prev = next;
1016
          b_elt = b_elt->next;
1017
        }
1018
      else
1019
        {
1020
          /* Matching elts, generate A = ~A & B.  */
1021
          unsigned ix;
1022
          BITMAP_WORD ior = 0;
1023
 
1024
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1025
            {
1026
              BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1027
              BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
1028
 
1029
              a_elt->bits[ix] = r;
1030
              ior |= r;
1031
            }
1032
          next = a_elt->next;
1033
          if (!ior)
1034
            bitmap_element_free (a, a_elt);
1035
          else
1036
            a_prev = a_elt;
1037
          a_elt = next;
1038
          b_elt = b_elt->next;
1039
        }
1040
    }
1041
  gcc_assert (!a->current == !a->first);
1042
  gcc_assert (!a->current || a->indx == a->current->indx);
1043
  return;
1044
}
1045
 
1046
/* DST = A | B.  Return true if DST changes.  */
1047
 
1048
bool
1049
bitmap_ior (bitmap dst, bitmap a, bitmap b)
1050
{
1051
  bitmap_element *dst_elt = dst->first;
1052
  bitmap_element *a_elt = a->first;
1053
  bitmap_element *b_elt = b->first;
1054
  bitmap_element *dst_prev = NULL;
1055
  bool changed = false;
1056
 
1057
  gcc_assert (dst != a && dst != b);
1058
 
1059
  while (a_elt || b_elt)
1060
    {
1061
      if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1062
        {
1063
          /* Matching elts, generate A | B.  */
1064
          unsigned ix;
1065
 
1066
          if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1067
            {
1068
              for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1069
                {
1070
                  BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1071
 
1072
                  if (r != dst_elt->bits[ix])
1073
                    {
1074
                      dst_elt->bits[ix] = r;
1075
                      changed = true;
1076
                    }
1077
                }
1078
            }
1079
          else
1080
            {
1081
              changed = true;
1082
              if (!dst_elt)
1083
                dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1084
              else
1085
                dst_elt->indx = a_elt->indx;
1086
              for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1087
                {
1088
                  BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1089
 
1090
                  dst_elt->bits[ix] = r;
1091
                }
1092
            }
1093
          a_elt = a_elt->next;
1094
          b_elt = b_elt->next;
1095
          dst_prev = dst_elt;
1096
          dst_elt = dst_elt->next;
1097
        }
1098
      else
1099
        {
1100
          /* Copy a single element.  */
1101
          bitmap_element *src;
1102
 
1103
          if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1104
            {
1105
              src = a_elt;
1106
              a_elt = a_elt->next;
1107
            }
1108
          else
1109
            {
1110
              src = b_elt;
1111
              b_elt = b_elt->next;
1112
            }
1113
 
1114
          if (!changed && dst_elt && dst_elt->indx == src->indx)
1115
            {
1116
              unsigned ix;
1117
 
1118
              for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1119
                if (src->bits[ix] != dst_elt->bits[ix])
1120
                  {
1121
                    dst_elt->bits[ix] = src->bits[ix];
1122
                    changed = true;
1123
                  }
1124
            }
1125
          else
1126
            {
1127
              changed = true;
1128
              if (!dst_elt)
1129
                dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1130
              else
1131
                dst_elt->indx = src->indx;
1132
              memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1133
            }
1134
 
1135
          dst_prev = dst_elt;
1136
          dst_elt = dst_elt->next;
1137
        }
1138
    }
1139
 
1140
  if (dst_elt)
1141
    {
1142
      changed = true;
1143
      bitmap_elt_clear_from (dst, dst_elt);
1144
    }
1145
  gcc_assert (!dst->current == !dst->first);
1146
  if (dst->current)
1147
    dst->indx = dst->current->indx;
1148
  return changed;
1149
}
1150
 
1151
/* A |= B.  Return true if A changes.  */
1152
 
1153
bool
1154
bitmap_ior_into (bitmap a, bitmap b)
1155
{
1156
  bitmap_element *a_elt = a->first;
1157
  bitmap_element *b_elt = b->first;
1158
  bitmap_element *a_prev = NULL;
1159
  bool changed = false;
1160
 
1161
  if (a == b)
1162
    return false;
1163
 
1164
  while (b_elt)
1165
    {
1166
      if (!a_elt || b_elt->indx < a_elt->indx)
1167
        {
1168
          /* Copy b_elt.  */
1169
          bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1170
          memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1171
          a_prev = dst;
1172
          b_elt = b_elt->next;
1173
          changed = true;
1174
        }
1175
      else if (a_elt->indx < b_elt->indx)
1176
        {
1177
          a_prev = a_elt;
1178
          a_elt = a_elt->next;
1179
        }
1180
      else
1181
        {
1182
          /* Matching elts, generate A |= B.  */
1183
          unsigned ix;
1184
 
1185
          if (changed)
1186
            for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1187
              {
1188
                BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1189
 
1190
                a_elt->bits[ix] = r;
1191
              }
1192
          else
1193
            for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1194
              {
1195
                BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1196
 
1197
                if (a_elt->bits[ix] != r)
1198
                  {
1199
                    changed = true;
1200
                    a_elt->bits[ix] = r;
1201
                  }
1202
              }
1203
          b_elt = b_elt->next;
1204
          a_prev = a_elt;
1205
          a_elt = a_elt->next;
1206
        }
1207
    }
1208
  gcc_assert (!a->current == !a->first);
1209
  if (a->current)
1210
    a->indx = a->current->indx;
1211
  return changed;
1212
}
1213
 
1214
/* DST = A ^ B  */
1215
 
1216
void
1217
bitmap_xor (bitmap dst, bitmap a, bitmap b)
1218
{
1219
  bitmap_element *dst_elt = dst->first;
1220
  bitmap_element *a_elt = a->first;
1221
  bitmap_element *b_elt = b->first;
1222
  bitmap_element *dst_prev = NULL;
1223
 
1224
  gcc_assert (dst != a && dst != b);
1225
  if (a == b)
1226
    {
1227
      bitmap_clear (dst);
1228
      return;
1229
    }
1230
 
1231
  while (a_elt || b_elt)
1232
    {
1233
      if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1234
        {
1235
          /* Matching elts, generate A ^ B.  */
1236
          unsigned ix;
1237
          BITMAP_WORD ior = 0;
1238
 
1239
          if (!dst_elt)
1240
            dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1241
          else
1242
            dst_elt->indx = a_elt->indx;
1243
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1244
            {
1245
              BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1246
 
1247
              ior |= r;
1248
              dst_elt->bits[ix] = r;
1249
            }
1250
          a_elt = a_elt->next;
1251
          b_elt = b_elt->next;
1252
          if (ior)
1253
            {
1254
              dst_prev = dst_elt;
1255
              dst_elt = dst_elt->next;
1256
            }
1257
        }
1258
      else
1259
        {
1260
          /* Copy a single element.  */
1261
          bitmap_element *src;
1262
 
1263
          if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1264
            {
1265
              src = a_elt;
1266
              a_elt = a_elt->next;
1267
            }
1268
          else
1269
            {
1270
              src = b_elt;
1271
              b_elt = b_elt->next;
1272
            }
1273
 
1274
          if (!dst_elt)
1275
            dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1276
          else
1277
            dst_elt->indx = src->indx;
1278
          memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1279
          dst_prev = dst_elt;
1280
          dst_elt = dst_elt->next;
1281
        }
1282
    }
1283
  bitmap_elt_clear_from (dst, dst_elt);
1284
  gcc_assert (!dst->current == !dst->first);
1285
  if (dst->current)
1286
    dst->indx = dst->current->indx;
1287
}
1288
 
1289
/* A ^= B */
1290
 
1291
void
1292
bitmap_xor_into (bitmap a, bitmap b)
1293
{
1294
  bitmap_element *a_elt = a->first;
1295
  bitmap_element *b_elt = b->first;
1296
  bitmap_element *a_prev = NULL;
1297
 
1298
  if (a == b)
1299
    {
1300
      bitmap_clear (a);
1301
      return;
1302
    }
1303
 
1304
  while (b_elt)
1305
    {
1306
      if (!a_elt || b_elt->indx < a_elt->indx)
1307
        {
1308
          /* Copy b_elt.  */
1309
          bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1310
          memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1311
          a_prev = dst;
1312
          b_elt = b_elt->next;
1313
        }
1314
      else if (a_elt->indx < b_elt->indx)
1315
        {
1316
          a_prev = a_elt;
1317
          a_elt = a_elt->next;
1318
        }
1319
      else
1320
        {
1321
          /* Matching elts, generate A ^= B.  */
1322
          unsigned ix;
1323
          BITMAP_WORD ior = 0;
1324
          bitmap_element *next = a_elt->next;
1325
 
1326
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1327
            {
1328
              BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1329
 
1330
              ior |= r;
1331
              a_elt->bits[ix] = r;
1332
            }
1333
          b_elt = b_elt->next;
1334
          if (ior)
1335
            a_prev = a_elt;
1336
          else
1337
            bitmap_element_free (a, a_elt);
1338
          a_elt = next;
1339
        }
1340
    }
1341
  gcc_assert (!a->current == !a->first);
1342
  if (a->current)
1343
    a->indx = a->current->indx;
1344
}
1345
 
1346
/* Return true if two bitmaps are identical.
1347
   We do not bother with a check for pointer equality, as that never
1348
   occurs in practice.  */
1349
 
1350
bool
1351
bitmap_equal_p (bitmap a, bitmap b)
1352
{
1353
  bitmap_element *a_elt;
1354
  bitmap_element *b_elt;
1355
  unsigned ix;
1356
 
1357
  for (a_elt = a->first, b_elt = b->first;
1358
       a_elt && b_elt;
1359
       a_elt = a_elt->next, b_elt = b_elt->next)
1360
    {
1361
      if (a_elt->indx != b_elt->indx)
1362
        return false;
1363
      for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1364
        if (a_elt->bits[ix] != b_elt->bits[ix])
1365
          return false;
1366
    }
1367
  return !a_elt && !b_elt;
1368
}
1369
 
1370
/* Return true if A AND B is not empty.  */
1371
 
1372
bool
1373
bitmap_intersect_p (bitmap a, bitmap b)
1374
{
1375
  bitmap_element *a_elt;
1376
  bitmap_element *b_elt;
1377
  unsigned ix;
1378
 
1379
  for (a_elt = a->first, b_elt = b->first;
1380
       a_elt && b_elt;)
1381
    {
1382
      if (a_elt->indx < b_elt->indx)
1383
        a_elt = a_elt->next;
1384
      else if (b_elt->indx < a_elt->indx)
1385
        b_elt = b_elt->next;
1386
      else
1387
        {
1388
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1389
            if (a_elt->bits[ix] & b_elt->bits[ix])
1390
              return true;
1391
          a_elt = a_elt->next;
1392
          b_elt = b_elt->next;
1393
        }
1394
    }
1395
  return false;
1396
}
1397
 
1398
/* Return true if A AND NOT B is not empty.  */
1399
 
1400
bool
1401
bitmap_intersect_compl_p (bitmap a, bitmap b)
1402
{
1403
  bitmap_element *a_elt;
1404
  bitmap_element *b_elt;
1405
  unsigned ix;
1406
  for (a_elt = a->first, b_elt = b->first;
1407
       a_elt && b_elt;)
1408
    {
1409
      if (a_elt->indx < b_elt->indx)
1410
        return true;
1411
      else if (b_elt->indx < a_elt->indx)
1412
        b_elt = b_elt->next;
1413
      else
1414
        {
1415
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1416
            if (a_elt->bits[ix] & ~b_elt->bits[ix])
1417
              return true;
1418
          a_elt = a_elt->next;
1419
          b_elt = b_elt->next;
1420
        }
1421
    }
1422
  return a_elt != NULL;
1423
}
1424
 
1425
 
1426
/* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
1427
 
1428
bool
1429
bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2)
1430
{
1431
  bitmap_head tmp;
1432
  bool changed;
1433
 
1434
  bitmap_initialize (&tmp, &bitmap_default_obstack);
1435
  bitmap_and_compl (&tmp, from1, from2);
1436
  changed = bitmap_ior (dst, a, &tmp);
1437
  bitmap_clear (&tmp);
1438
 
1439
  return changed;
1440
}
1441
 
1442
/* A |= (FROM1 & ~FROM2).  Return true if A changes.  */
1443
 
1444
bool
1445
bitmap_ior_and_compl_into (bitmap a, bitmap from1, bitmap from2)
1446
{
1447
  bitmap_head tmp;
1448
  bool changed;
1449
 
1450
  bitmap_initialize (&tmp, &bitmap_default_obstack);
1451
  bitmap_and_compl (&tmp, from1, from2);
1452
  changed = bitmap_ior_into (a, &tmp);
1453
  bitmap_clear (&tmp);
1454
 
1455
  return changed;
1456
}
1457
 
1458
/* Debugging function to print out the contents of a bitmap.  */
1459
 
1460
void
1461
debug_bitmap_file (FILE *file, bitmap head)
1462
{
1463
  bitmap_element *ptr;
1464
 
1465
  fprintf (file, "\nfirst = %p current = %p indx = %u\n",
1466
           (void *) head->first, (void *) head->current, head->indx);
1467
 
1468
  for (ptr = head->first; ptr; ptr = ptr->next)
1469
    {
1470
      unsigned int i, j, col = 26;
1471
 
1472
      fprintf (file, "\t%p next = %p prev = %p indx = %u\n\t\tbits = {",
1473
               (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx);
1474
 
1475
      for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1476
        for (j = 0; j < BITMAP_WORD_BITS; j++)
1477
          if ((ptr->bits[i] >> j) & 1)
1478
            {
1479
              if (col > 70)
1480
                {
1481
                  fprintf (file, "\n\t\t\t");
1482
                  col = 24;
1483
                }
1484
 
1485
              fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
1486
                                     + i * BITMAP_WORD_BITS + j));
1487
              col += 4;
1488
            }
1489
 
1490
      fprintf (file, " }\n");
1491
    }
1492
}
1493
 
1494
/* Function to be called from the debugger to print the contents
1495
   of a bitmap.  */
1496
 
1497
void
1498
debug_bitmap (bitmap head)
1499
{
1500
  debug_bitmap_file (stdout, head);
1501
}
1502
 
1503
/* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
1504
   it does not print anything but the bits.  */
1505
 
1506
void
1507
bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
1508
{
1509
  const char *comma = "";
1510
  unsigned i;
1511
  bitmap_iterator bi;
1512
 
1513
  fputs (prefix, file);
1514
  EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
1515
    {
1516
      fprintf (file, "%s%d", comma, i);
1517
      comma = ", ";
1518
    }
1519
  fputs (suffix, file);
1520
}
1521
 
1522
/* Compute hash of bitmap (for purposes of hashing).  */
1523
hashval_t
1524
bitmap_hash (bitmap head)
1525
{
1526
  bitmap_element *ptr;
1527
  BITMAP_WORD hash = 0;
1528
  int ix;
1529
 
1530
  for (ptr = head->first; ptr; ptr = ptr->next)
1531
    {
1532
      hash ^= ptr->indx;
1533
      for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1534
        hash ^= ptr->bits[ix];
1535
    }
1536
  return (hashval_t)hash;
1537
}
1538
 
1539
#include "gt-bitmap.h"

powered by: WebSVN 2.1.0

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