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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [bitmap.c] - Blame information for rev 826

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Functions to support general ended bitmaps.
2
   Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005,
3
   2006, 2007, 2008, 2009 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
#include "hashtab.h"
31
 
32
#ifdef GATHER_STATISTICS
33
 
34
/* Store information about each particular bitmap.  */
35
struct bitmap_descriptor
36
{
37
  const char *function;
38
  const char *file;
39
  int line;
40
  int created;
41
  HOST_WIDEST_INT allocated;
42
  HOST_WIDEST_INT peak;
43
  HOST_WIDEST_INT current;
44
  int nsearches;
45
};
46
 
47
/* Hashtable mapping bitmap names to descriptors.  */
48
static htab_t bitmap_desc_hash;
49
 
50
/* Hashtable helpers.  */
51
static hashval_t
52
hash_descriptor (const void *p)
53
{
54
  const struct bitmap_descriptor *const d =
55
    (const struct bitmap_descriptor *) p;
56
  return htab_hash_pointer (d->file) + d->line;
57
}
58
struct loc
59
{
60
  const char *file;
61
  const char *function;
62
  int line;
63
};
64
static int
65
eq_descriptor (const void *p1, const void *p2)
66
{
67
  const struct bitmap_descriptor *const d =
68
    (const struct bitmap_descriptor *) p1;
69
  const struct loc *const l = (const struct loc *) p2;
70
  return d->file == l->file && d->function == l->function && d->line == l->line;
71
}
72
 
73
/* For given file and line, return descriptor, create new if needed.  */
74
static struct bitmap_descriptor *
75
bitmap_descriptor (const char *file, const char *function, int line)
76
{
77
  struct bitmap_descriptor **slot;
78
  struct loc loc;
79
 
80
  loc.file = file;
81
  loc.function = function;
82
  loc.line = line;
83
 
84
  if (!bitmap_desc_hash)
85
    bitmap_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
86
 
87
  slot = (struct bitmap_descriptor **)
88
    htab_find_slot_with_hash (bitmap_desc_hash, &loc,
89
                              htab_hash_pointer (file) + line,
90
                              INSERT);
91
  if (*slot)
92
    return *slot;
93
  *slot = XCNEW (struct bitmap_descriptor);
94
  (*slot)->file = file;
95
  (*slot)->function = function;
96
  (*slot)->line = line;
97
  return *slot;
98
}
99
 
100
/* Register new bitmap.  */
101
void
102
bitmap_register (bitmap b MEM_STAT_DECL)
103
{
104
  b->desc = bitmap_descriptor (_loc_name, _loc_function, _loc_line);
105
  b->desc->created++;
106
}
107
 
108
/* Account the overhead.  */
109
static void
110
register_overhead (bitmap b, int amount)
111
{
112
  b->desc->current += amount;
113
  if (amount > 0)
114
    b->desc->allocated += amount;
115
  gcc_assert (b->desc->current >= 0);
116
  if (b->desc->peak < b->desc->current)
117
    b->desc->peak = b->desc->current;
118
}
119
#endif
120
 
121
/* Global data */
122
bitmap_element bitmap_zero_bits;  /* An element of all zero bits.  */
123
bitmap_obstack bitmap_default_obstack;    /* The default bitmap obstack.  */
124
static int bitmap_default_obstack_depth;
125
static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
126
                                                            GC'd elements.  */
127
 
128
static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
129
static void bitmap_element_free (bitmap, bitmap_element *);
130
static bitmap_element *bitmap_element_allocate (bitmap);
131
static int bitmap_element_zerop (const bitmap_element *);
132
static void bitmap_element_link (bitmap, bitmap_element *);
133
static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);
134
static void bitmap_elt_clear_from (bitmap, bitmap_element *);
135
static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
136
 
137
 
138
/* Add ELEM to the appropriate freelist.  */
139
static inline void
140
bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
141
{
142
  bitmap_obstack *bit_obstack = head->obstack;
143
 
144
  elt->next = NULL;
145
  if (bit_obstack)
146
    {
147
      elt->prev = bit_obstack->elements;
148
      bit_obstack->elements = elt;
149
    }
150
  else
151
    {
152
      elt->prev = bitmap_ggc_free;
153
      bitmap_ggc_free = elt;
154
    }
155
}
156
 
157
/* Free a bitmap element.  Since these are allocated off the
158
   bitmap_obstack, "free" actually means "put onto the freelist".  */
159
 
160
static inline void
161
bitmap_element_free (bitmap head, bitmap_element *elt)
162
{
163
  bitmap_element *next = elt->next;
164
  bitmap_element *prev = elt->prev;
165
 
166
  if (prev)
167
    prev->next = next;
168
 
169
  if (next)
170
    next->prev = prev;
171
 
172
  if (head->first == elt)
173
    head->first = next;
174
 
175
  /* Since the first thing we try is to insert before current,
176
     make current the next entry in preference to the previous.  */
177
  if (head->current == elt)
178
    {
179
      head->current = next != 0 ? next : prev;
180
      if (head->current)
181
        head->indx = head->current->indx;
182
      else
183
        head->indx = 0;
184
    }
185
#ifdef GATHER_STATISTICS
186
  register_overhead (head, -((int)sizeof (bitmap_element)));
187
#endif
188
  bitmap_elem_to_freelist (head, elt);
189
}
190
 
191
/* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
192
 
193
static inline bitmap_element *
194
bitmap_element_allocate (bitmap head)
195
{
196
  bitmap_element *element;
197
  bitmap_obstack *bit_obstack = head->obstack;
198
 
199
  if (bit_obstack)
200
    {
201
      element = bit_obstack->elements;
202
 
203
      if (element)
204
        /* Use up the inner list first before looking at the next
205
           element of the outer list.  */
206
        if (element->next)
207
          {
208
            bit_obstack->elements = element->next;
209
            bit_obstack->elements->prev = element->prev;
210
          }
211
        else
212
          /*  Inner list was just a singleton.  */
213
          bit_obstack->elements = element->prev;
214
      else
215
        element = XOBNEW (&bit_obstack->obstack, bitmap_element);
216
    }
217
  else
218
    {
219
      element = bitmap_ggc_free;
220
      if (element)
221
        /* Use up the inner list first before looking at the next
222
           element of the outer list.  */
223
        if (element->next)
224
          {
225
            bitmap_ggc_free = element->next;
226
            bitmap_ggc_free->prev = element->prev;
227
          }
228
        else
229
          /*  Inner list was just a singleton.  */
230
          bitmap_ggc_free = element->prev;
231
      else
232
        element = GGC_NEW (bitmap_element);
233
    }
234
 
235
#ifdef GATHER_STATISTICS
236
  register_overhead (head, sizeof (bitmap_element));
237
#endif
238
  memset (element->bits, 0, sizeof (element->bits));
239
 
240
  return element;
241
}
242
 
243
/* Remove ELT and all following elements from bitmap HEAD.  */
244
 
245
void
246
bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
247
{
248
  bitmap_element *prev;
249
  bitmap_obstack *bit_obstack = head->obstack;
250
#ifdef GATHER_STATISTICS
251
  int n;
252
#endif
253
 
254
  if (!elt) return;
255
#ifdef GATHER_STATISTICS
256
  n = 0;
257
  for (prev = elt; prev; prev = prev->next)
258
    n++;
259
  register_overhead (head, -sizeof (bitmap_element) * n);
260
#endif
261
 
262
  prev = elt->prev;
263
  if (prev)
264
    {
265
      prev->next = NULL;
266
      if (head->current->indx > prev->indx)
267
        {
268
          head->current = prev;
269
          head->indx = prev->indx;
270
        }
271
    }
272
  else
273
    {
274
      head->first = NULL;
275
      head->current = NULL;
276
      head->indx = 0;
277
    }
278
 
279
  /* Put the entire list onto the free list in one operation. */
280
  if (bit_obstack)
281
    {
282
      elt->prev = bit_obstack->elements;
283
      bit_obstack->elements = elt;
284
    }
285
  else
286
    {
287
      elt->prev = bitmap_ggc_free;
288
      bitmap_ggc_free = elt;
289
    }
290
}
291
 
292
/* Clear a bitmap by freeing the linked list.  */
293
 
294
void
295
bitmap_clear (bitmap head)
296
{
297
  if (head->first)
298
    bitmap_elt_clear_from (head, head->first);
299
}
300
 
301
/* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
302
   the default bitmap obstack.  */
303
 
304
void
305
bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
306
{
307
  if (!bit_obstack)
308
    {
309
      if (bitmap_default_obstack_depth++)
310
        return;
311
      bit_obstack = &bitmap_default_obstack;
312
    }
313
 
314
#if !defined(__GNUC__) || (__GNUC__ < 2)
315
#define __alignof__(type) 0
316
#endif
317
 
318
  bit_obstack->elements = NULL;
319
  bit_obstack->heads = NULL;
320
  obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
321
                              __alignof__ (bitmap_element),
322
                              obstack_chunk_alloc,
323
                              obstack_chunk_free);
324
}
325
 
326
/* Release the memory from a bitmap obstack.  If BIT_OBSTACK is NULL,
327
   release the default bitmap obstack.  */
328
 
329
void
330
bitmap_obstack_release (bitmap_obstack *bit_obstack)
331
{
332
  if (!bit_obstack)
333
    {
334
      if (--bitmap_default_obstack_depth)
335
        {
336
          gcc_assert (bitmap_default_obstack_depth > 0);
337
          return;
338
        }
339
      bit_obstack = &bitmap_default_obstack;
340
    }
341
 
342
  bit_obstack->elements = NULL;
343
  bit_obstack->heads = NULL;
344
  obstack_free (&bit_obstack->obstack, NULL);
345
}
346
 
347
/* Create a new bitmap on an obstack.  If BIT_OBSTACK is NULL, create
348
   it on the default bitmap obstack.  */
349
 
350
bitmap
351
bitmap_obstack_alloc_stat (bitmap_obstack *bit_obstack MEM_STAT_DECL)
352
{
353
  bitmap map;
354
 
355
  if (!bit_obstack)
356
    bit_obstack = &bitmap_default_obstack;
357
  map = bit_obstack->heads;
358
  if (map)
359
    bit_obstack->heads = (struct bitmap_head_def *) map->first;
360
  else
361
    map = XOBNEW (&bit_obstack->obstack, bitmap_head);
362
  bitmap_initialize_stat (map, bit_obstack PASS_MEM_STAT);
363
#ifdef GATHER_STATISTICS
364
  register_overhead (map, sizeof (bitmap_head));
365
#endif
366
 
367
  return map;
368
}
369
 
370
/* Create a new GCd bitmap.  */
371
 
372
bitmap
373
bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL)
374
{
375
  bitmap map;
376
 
377
  map = GGC_NEW (struct bitmap_head_def);
378
  bitmap_initialize_stat (map, NULL PASS_MEM_STAT);
379
#ifdef GATHER_STATISTICS
380
  register_overhead (map, sizeof (bitmap_head));
381
#endif
382
 
383
  return map;
384
}
385
 
386
/* Release an obstack allocated bitmap.  */
387
 
388
void
389
bitmap_obstack_free (bitmap map)
390
{
391
  if (map)
392
    {
393
      bitmap_clear (map);
394
      map->first = (bitmap_element *) map->obstack->heads;
395
#ifdef GATHER_STATISTICS
396
      register_overhead (map, -((int)sizeof (bitmap_head)));
397
#endif
398
      map->obstack->heads = map;
399
    }
400
}
401
 
402
 
403
/* Return nonzero if all bits in an element are zero.  */
404
 
405
static inline int
406
bitmap_element_zerop (const bitmap_element *element)
407
{
408
#if BITMAP_ELEMENT_WORDS == 2
409
  return (element->bits[0] | element->bits[1]) == 0;
410
#else
411
  unsigned i;
412
 
413
  for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
414
    if (element->bits[i] != 0)
415
      return 0;
416
 
417
  return 1;
418
#endif
419
}
420
 
421
/* Link the bitmap element into the current bitmap linked list.  */
422
 
423
static inline void
424
bitmap_element_link (bitmap head, bitmap_element *element)
425
{
426
  unsigned int indx = element->indx;
427
  bitmap_element *ptr;
428
 
429
  /* If this is the first and only element, set it in.  */
430
  if (head->first == 0)
431
    {
432
      element->next = element->prev = 0;
433
      head->first = element;
434
    }
435
 
436
  /* If this index is less than that of the current element, it goes someplace
437
     before the current element.  */
438
  else if (indx < head->indx)
439
    {
440
      for (ptr = head->current;
441
           ptr->prev != 0 && ptr->prev->indx > indx;
442
           ptr = ptr->prev)
443
        ;
444
 
445
      if (ptr->prev)
446
        ptr->prev->next = element;
447
      else
448
        head->first = element;
449
 
450
      element->prev = ptr->prev;
451
      element->next = ptr;
452
      ptr->prev = element;
453
    }
454
 
455
  /* Otherwise, it must go someplace after the current element.  */
456
  else
457
    {
458
      for (ptr = head->current;
459
           ptr->next != 0 && ptr->next->indx < indx;
460
           ptr = ptr->next)
461
        ;
462
 
463
      if (ptr->next)
464
        ptr->next->prev = element;
465
 
466
      element->next = ptr->next;
467
      element->prev = ptr;
468
      ptr->next = element;
469
    }
470
 
471
  /* Set up so this is the first element searched.  */
472
  head->current = element;
473
  head->indx = indx;
474
}
475
 
476
/* Insert a new uninitialized element into bitmap HEAD after element
477
   ELT.  If ELT is NULL, insert the element at the start.  Return the
478
   new element.  */
479
 
480
static bitmap_element *
481
bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
482
{
483
  bitmap_element *node = bitmap_element_allocate (head);
484
  node->indx = indx;
485
 
486
  if (!elt)
487
    {
488
      if (!head->current)
489
        {
490
          head->current = node;
491
          head->indx = indx;
492
        }
493
      node->next = head->first;
494
      if (node->next)
495
        node->next->prev = node;
496
      head->first = node;
497
      node->prev = NULL;
498
    }
499
  else
500
    {
501
      gcc_assert (head->current);
502
      node->next = elt->next;
503
      if (node->next)
504
        node->next->prev = node;
505
      elt->next = node;
506
      node->prev = elt;
507
    }
508
  return node;
509
}
510
 
511
/* Copy a bitmap to another bitmap.  */
512
 
513
void
514
bitmap_copy (bitmap to, const_bitmap from)
515
{
516
  const bitmap_element *from_ptr;
517
  bitmap_element *to_ptr = 0;
518
 
519
  bitmap_clear (to);
520
 
521
  /* Copy elements in forward direction one at a time.  */
522
  for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
523
    {
524
      bitmap_element *to_elt = bitmap_element_allocate (to);
525
 
526
      to_elt->indx = from_ptr->indx;
527
      memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
528
 
529
      /* Here we have a special case of bitmap_element_link, for the case
530
         where we know the links are being entered in sequence.  */
531
      if (to_ptr == 0)
532
        {
533
          to->first = to->current = to_elt;
534
          to->indx = from_ptr->indx;
535
          to_elt->next = to_elt->prev = 0;
536
        }
537
      else
538
        {
539
          to_elt->prev = to_ptr;
540
          to_elt->next = 0;
541
          to_ptr->next = to_elt;
542
        }
543
 
544
      to_ptr = to_elt;
545
    }
546
}
547
 
548
/* Find a bitmap element that would hold a bitmap's bit.
549
   Update the `current' field even if we can't find an element that
550
   would hold the bitmap's bit to make eventual allocation
551
   faster.  */
552
 
553
static inline bitmap_element *
554
bitmap_find_bit (bitmap head, unsigned int bit)
555
{
556
  bitmap_element *element;
557
  unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
558
 
559
#ifdef GATHER_STATISTICS
560
  head->desc->nsearches++;
561
#endif
562
  if (head->current == 0
563
      || head->indx == indx)
564
    return head->current;
565
 
566
  if (head->indx < indx)
567
    /* INDX is beyond head->indx.  Search from head->current
568
       forward.  */
569
    for (element = head->current;
570
         element->next != 0 && element->indx < indx;
571
         element = element->next)
572
      ;
573
 
574
  else if (head->indx / 2 < indx)
575
    /* INDX is less than head->indx and closer to head->indx than to
576
       0.  Search from head->current backward.  */
577
    for (element = head->current;
578
         element->prev != 0 && element->indx > indx;
579
         element = element->prev)
580
      ;
581
 
582
  else
583
    /* INDX is less than head->indx and closer to 0 than to
584
       head->indx.  Search from head->first forward.  */
585
    for (element = head->first;
586
         element->next != 0 && element->indx < indx;
587
         element = element->next)
588
      ;
589
 
590
  /* `element' is the nearest to the one we want.  If it's not the one we
591
     want, the one we want doesn't exist.  */
592
  head->current = element;
593
  head->indx = element->indx;
594
  if (element != 0 && element->indx != indx)
595
    element = 0;
596
 
597
  return element;
598
}
599
 
600
/* Clear a single bit in a bitmap.  Return true if the bit changed.  */
601
 
602
bool
603
bitmap_clear_bit (bitmap head, int bit)
604
{
605
  bitmap_element *const ptr = bitmap_find_bit (head, bit);
606
 
607
  if (ptr != 0)
608
    {
609
      unsigned bit_num  = bit % BITMAP_WORD_BITS;
610
      unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
611
      BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
612
      bool res = (ptr->bits[word_num] & bit_val) != 0;
613
      if (res)
614
        ptr->bits[word_num] &= ~bit_val;
615
 
616
      /* If we cleared the entire word, free up the element.  */
617
      if (bitmap_element_zerop (ptr))
618
        bitmap_element_free (head, ptr);
619
 
620
      return res;
621
    }
622
 
623
  return false;
624
}
625
 
626
/* Set a single bit in a bitmap.  Return true if the bit changed.  */
627
 
628
bool
629
bitmap_set_bit (bitmap head, int bit)
630
{
631
  bitmap_element *ptr = bitmap_find_bit (head, bit);
632
  unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
633
  unsigned bit_num  = bit % BITMAP_WORD_BITS;
634
  BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
635
 
636
  if (ptr == 0)
637
    {
638
      ptr = bitmap_element_allocate (head);
639
      ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
640
      ptr->bits[word_num] = bit_val;
641
      bitmap_element_link (head, ptr);
642
      return true;
643
    }
644
  else
645
    {
646
      bool res = (ptr->bits[word_num] & bit_val) == 0;
647
      if (res)
648
        ptr->bits[word_num] |= bit_val;
649
      return res;
650
    }
651
}
652
 
653
/* Return whether a bit is set within a bitmap.  */
654
 
655
int
656
bitmap_bit_p (bitmap head, int bit)
657
{
658
  bitmap_element *ptr;
659
  unsigned bit_num;
660
  unsigned word_num;
661
 
662
  ptr = bitmap_find_bit (head, bit);
663
  if (ptr == 0)
664
    return 0;
665
 
666
  bit_num = bit % BITMAP_WORD_BITS;
667
  word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
668
 
669
  return (ptr->bits[word_num] >> bit_num) & 1;
670
}
671
 
672
#if GCC_VERSION < 3400
673
/* Table of number of set bits in a character, indexed by value of char.  */
674
static const unsigned char popcount_table[] =
675
{
676
    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,
677
    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,
678
    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,
679
    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,
680
    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,
681
    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,
682
    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,
683
    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,
684
};
685
 
686
static unsigned long
687
bitmap_popcount (BITMAP_WORD a)
688
{
689
  unsigned long ret = 0;
690
  unsigned i;
691
 
692
  /* Just do this the table way for now  */
693
  for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
694
    ret += popcount_table[(a >> i) & 0xff];
695
  return ret;
696
}
697
#endif
698
/* Count the number of bits set in the bitmap, and return it.  */
699
 
700
unsigned long
701
bitmap_count_bits (const_bitmap a)
702
{
703
  unsigned long count = 0;
704
  const bitmap_element *elt;
705
  unsigned ix;
706
 
707
  for (elt = a->first; elt; elt = elt->next)
708
    {
709
      for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
710
        {
711
#if GCC_VERSION >= 3400
712
          /* Note that popcountl matches BITMAP_WORD in type, so the actual size
713
         of BITMAP_WORD is not material.  */
714
          count += __builtin_popcountl (elt->bits[ix]);
715
#else
716
          count += bitmap_popcount (elt->bits[ix]);
717
#endif
718
        }
719
    }
720
  return count;
721
}
722
 
723
/* Return true if the bitmap has a single bit set.  Otherwise return
724
   false.  */
725
 
726
bool
727
bitmap_single_bit_set_p (const_bitmap a)
728
{
729
  unsigned long count = 0;
730
  const bitmap_element *elt;
731
  unsigned ix;
732
 
733
  if (bitmap_empty_p (a))
734
    return false;
735
 
736
  elt = a->first;
737
  /* As there are no completely empty bitmap elements, a second one
738
     means we have more than one bit set.  */
739
  if (elt->next != NULL)
740
    return false;
741
 
742
  for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
743
    {
744
#if GCC_VERSION >= 3400
745
      /* Note that popcountl matches BITMAP_WORD in type, so the actual size
746
         of BITMAP_WORD is not material.  */
747
      count += __builtin_popcountl (elt->bits[ix]);
748
#else
749
      count += bitmap_popcount (elt->bits[ix]);
750
#endif
751
      if (count > 1)
752
        return false;
753
    }
754
 
755
  return count == 1;
756
}
757
 
758
 
759
/* Return the bit number of the first set bit in the bitmap.  The
760
   bitmap must be non-empty.  */
761
 
762
unsigned
763
bitmap_first_set_bit (const_bitmap a)
764
{
765
  const bitmap_element *elt = a->first;
766
  unsigned bit_no;
767
  BITMAP_WORD word;
768
  unsigned ix;
769
 
770
  gcc_assert (elt);
771
  bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
772
  for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
773
    {
774
      word = elt->bits[ix];
775
      if (word)
776
        goto found_bit;
777
    }
778
  gcc_unreachable ();
779
 found_bit:
780
  bit_no += ix * BITMAP_WORD_BITS;
781
 
782
#if GCC_VERSION >= 3004
783
  gcc_assert (sizeof(long) == sizeof (word));
784
  bit_no += __builtin_ctzl (word);
785
#else
786
  /* Binary search for the first set bit.  */
787
#if BITMAP_WORD_BITS > 64
788
#error "Fill out the table."
789
#endif
790
#if BITMAP_WORD_BITS > 32
791
  if (!(word & 0xffffffff))
792
    word >>= 32, bit_no += 32;
793
#endif
794
  if (!(word & 0xffff))
795
    word >>= 16, bit_no += 16;
796
  if (!(word & 0xff))
797
    word >>= 8, bit_no += 8;
798
  if (!(word & 0xf))
799
    word >>= 4, bit_no += 4;
800
  if (!(word & 0x3))
801
    word >>= 2, bit_no += 2;
802
  if (!(word & 0x1))
803
    word >>= 1, bit_no += 1;
804
 
805
 gcc_assert (word & 1);
806
#endif
807
 return bit_no;
808
}
809
 
810
/* Return the bit number of the first set bit in the bitmap.  The
811
   bitmap must be non-empty.  */
812
 
813
unsigned
814
bitmap_last_set_bit (const_bitmap a)
815
{
816
  const bitmap_element *elt = a->current ? a->current : a->first;
817
  unsigned bit_no;
818
  BITMAP_WORD word;
819
  int ix;
820
 
821
  gcc_assert (elt);
822
  while (elt->next)
823
    elt = elt->next;
824
  bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
825
  for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
826
    {
827
      word = elt->bits[ix];
828
      if (word)
829
        goto found_bit;
830
    }
831
  gcc_unreachable ();
832
 found_bit:
833
  bit_no += ix * BITMAP_WORD_BITS;
834
 
835
  /* Binary search for the last set bit.  */
836
#if GCC_VERSION >= 3004
837
  gcc_assert (sizeof(long) == sizeof (word));
838
  bit_no += sizeof (long) * 8 - __builtin_ctzl (word);
839
#else
840
#if BITMAP_WORD_BITS > 64
841
#error "Fill out the table."
842
#endif
843
#if BITMAP_WORD_BITS > 32
844
  if ((word & 0xffffffff00000000))
845
    word >>= 32, bit_no += 32;
846
#endif
847
  if (word & 0xffff0000)
848
    word >>= 16, bit_no += 16;
849
  if (!(word & 0xff00))
850
    word >>= 8, bit_no += 8;
851
  if (!(word & 0xf0))
852
    word >>= 4, bit_no += 4;
853
  if (!(word & 12))
854
    word >>= 2, bit_no += 2;
855
  if (!(word & 2))
856
    word >>= 1, bit_no += 1;
857
#endif
858
 
859
 gcc_assert (word & 1);
860
 return bit_no;
861
}
862
 
863
 
864
/* DST = A & B.  */
865
 
866
void
867
bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
868
{
869
  bitmap_element *dst_elt = dst->first;
870
  const bitmap_element *a_elt = a->first;
871
  const bitmap_element *b_elt = b->first;
872
  bitmap_element *dst_prev = NULL;
873
 
874
  gcc_assert (dst != a && dst != b);
875
 
876
  if (a == b)
877
    {
878
      bitmap_copy (dst, a);
879
      return;
880
    }
881
 
882
  while (a_elt && b_elt)
883
    {
884
      if (a_elt->indx < b_elt->indx)
885
        a_elt = a_elt->next;
886
      else if (b_elt->indx < a_elt->indx)
887
        b_elt = b_elt->next;
888
      else
889
        {
890
          /* Matching elts, generate A & B.  */
891
          unsigned ix;
892
          BITMAP_WORD ior = 0;
893
 
894
          if (!dst_elt)
895
            dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
896
          else
897
            dst_elt->indx = a_elt->indx;
898
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
899
            {
900
              BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
901
 
902
              dst_elt->bits[ix] = r;
903
              ior |= r;
904
            }
905
          if (ior)
906
            {
907
              dst_prev = dst_elt;
908
              dst_elt = dst_elt->next;
909
            }
910
          a_elt = a_elt->next;
911
          b_elt = b_elt->next;
912
        }
913
    }
914
  /* Ensure that dst->current is valid.  */
915
  dst->current = dst->first;
916
  bitmap_elt_clear_from (dst, dst_elt);
917
  gcc_assert (!dst->current == !dst->first);
918
  if (dst->current)
919
    dst->indx = dst->current->indx;
920
}
921
 
922
/* A &= B.  */
923
 
924
void
925
bitmap_and_into (bitmap a, const_bitmap b)
926
{
927
  bitmap_element *a_elt = a->first;
928
  const bitmap_element *b_elt = b->first;
929
  bitmap_element *next;
930
 
931
  if (a == b)
932
    return;
933
 
934
  while (a_elt && b_elt)
935
    {
936
      if (a_elt->indx < b_elt->indx)
937
        {
938
          next = a_elt->next;
939
          bitmap_element_free (a, a_elt);
940
          a_elt = next;
941
        }
942
      else if (b_elt->indx < a_elt->indx)
943
        b_elt = b_elt->next;
944
      else
945
        {
946
          /* Matching elts, generate A &= B.  */
947
          unsigned ix;
948
          BITMAP_WORD ior = 0;
949
 
950
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
951
            {
952
              BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
953
 
954
              a_elt->bits[ix] = r;
955
              ior |= r;
956
            }
957
          next = a_elt->next;
958
          if (!ior)
959
            bitmap_element_free (a, a_elt);
960
          a_elt = next;
961
          b_elt = b_elt->next;
962
        }
963
    }
964
  bitmap_elt_clear_from (a, a_elt);
965
  gcc_assert (!a->current == !a->first);
966
  gcc_assert (!a->current || a->indx == a->current->indx);
967
}
968
 
969
 
970
/* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
971
   if non-NULL.  CHANGED is true if the destination bitmap had already been
972
   changed; the new value of CHANGED is returned.  */
973
 
974
static inline bool
975
bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
976
                 const bitmap_element *src_elt, bool changed)
977
{
978
  if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
979
    {
980
      unsigned ix;
981
 
982
      for (ix = BITMAP_ELEMENT_WORDS; ix--;)
983
        if (src_elt->bits[ix] != dst_elt->bits[ix])
984
          {
985
            dst_elt->bits[ix] = src_elt->bits[ix];
986
            changed = true;
987
          }
988
    }
989
  else
990
    {
991
      changed = true;
992
      if (!dst_elt)
993
        dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx);
994
      else
995
        dst_elt->indx = src_elt->indx;
996
      memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
997
    }
998
  return changed;
999
}
1000
 
1001
 
1002
 
1003
/* DST = A & ~B  */
1004
 
1005
bool
1006
bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
1007
{
1008
  bitmap_element *dst_elt = dst->first;
1009
  const bitmap_element *a_elt = a->first;
1010
  const bitmap_element *b_elt = b->first;
1011
  bitmap_element *dst_prev = NULL;
1012
  bitmap_element **dst_prev_pnext = &dst->first;
1013
  bool changed = false;
1014
 
1015
  gcc_assert (dst != a && dst != b);
1016
 
1017
  if (a == b)
1018
    {
1019
      changed = !bitmap_empty_p (dst);
1020
      bitmap_clear (dst);
1021
      return changed;
1022
    }
1023
 
1024
  while (a_elt)
1025
    {
1026
      while (b_elt && b_elt->indx < a_elt->indx)
1027
        b_elt = b_elt->next;
1028
 
1029
      if (!b_elt || b_elt->indx > a_elt->indx)
1030
        {
1031
          changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
1032
          dst_prev = *dst_prev_pnext;
1033
          dst_prev_pnext = &dst_prev->next;
1034
          dst_elt = *dst_prev_pnext;
1035
          a_elt = a_elt->next;
1036
        }
1037
 
1038
      else
1039
        {
1040
          /* Matching elts, generate A & ~B.  */
1041
          unsigned ix;
1042
          BITMAP_WORD ior = 0;
1043
 
1044
          if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1045
            {
1046
              for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1047
                {
1048
                  BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1049
 
1050
                  if (dst_elt->bits[ix] != r)
1051
                    {
1052
                      changed = true;
1053
                      dst_elt->bits[ix] = r;
1054
                    }
1055
                  ior |= r;
1056
                }
1057
            }
1058
          else
1059
            {
1060
              bool new_element;
1061
              if (!dst_elt || dst_elt->indx > a_elt->indx)
1062
                {
1063
                  dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1064
                  new_element = true;
1065
                }
1066
              else
1067
                {
1068
                  dst_elt->indx = a_elt->indx;
1069
                  new_element = false;
1070
                }
1071
 
1072
              for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1073
                {
1074
                  BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1075
 
1076
                  dst_elt->bits[ix] = r;
1077
                  ior |= r;
1078
                }
1079
 
1080
              if (ior)
1081
                changed = true;
1082
              else
1083
                {
1084
                  changed |= !new_element;
1085
                  bitmap_element_free (dst, dst_elt);
1086
                  dst_elt = *dst_prev_pnext;
1087
                }
1088
            }
1089
 
1090
          if (ior)
1091
            {
1092
              dst_prev = *dst_prev_pnext;
1093
              dst_prev_pnext = &dst_prev->next;
1094
              dst_elt = *dst_prev_pnext;
1095
            }
1096
          a_elt = a_elt->next;
1097
          b_elt = b_elt->next;
1098
        }
1099
    }
1100
 
1101
  /* Ensure that dst->current is valid.  */
1102
  dst->current = dst->first;
1103
 
1104
  if (dst_elt)
1105
    {
1106
      changed = true;
1107
      bitmap_elt_clear_from (dst, dst_elt);
1108
    }
1109
  gcc_assert (!dst->current == !dst->first);
1110
  if (dst->current)
1111
    dst->indx = dst->current->indx;
1112
 
1113
  return changed;
1114
}
1115
 
1116
/* A &= ~B. Returns true if A changes */
1117
 
1118
bool
1119
bitmap_and_compl_into (bitmap a, const_bitmap b)
1120
{
1121
  bitmap_element *a_elt = a->first;
1122
  const bitmap_element *b_elt = b->first;
1123
  bitmap_element *next;
1124
  BITMAP_WORD changed = 0;
1125
 
1126
  if (a == b)
1127
    {
1128
      if (bitmap_empty_p (a))
1129
        return false;
1130
      else
1131
        {
1132
          bitmap_clear (a);
1133
          return true;
1134
        }
1135
    }
1136
 
1137
  while (a_elt && b_elt)
1138
    {
1139
      if (a_elt->indx < b_elt->indx)
1140
        a_elt = a_elt->next;
1141
      else if (b_elt->indx < a_elt->indx)
1142
        b_elt = b_elt->next;
1143
      else
1144
        {
1145
          /* Matching elts, generate A &= ~B.  */
1146
          unsigned ix;
1147
          BITMAP_WORD ior = 0;
1148
 
1149
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1150
            {
1151
              BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1152
              BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
1153
 
1154
              a_elt->bits[ix] = r;
1155
              changed |= cleared;
1156
              ior |= r;
1157
            }
1158
          next = a_elt->next;
1159
          if (!ior)
1160
            bitmap_element_free (a, a_elt);
1161
          a_elt = next;
1162
          b_elt = b_elt->next;
1163
        }
1164
    }
1165
  gcc_assert (!a->current == !a->first);
1166
  gcc_assert (!a->current || a->indx == a->current->indx);
1167
  return changed != 0;
1168
}
1169
 
1170
/* Set COUNT bits from START in HEAD.  */
1171
void
1172
bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
1173
{
1174
  unsigned int first_index, end_bit_plus1, last_index;
1175
  bitmap_element *elt, *elt_prev;
1176
  unsigned int i;
1177
 
1178
  if (!count)
1179
    return;
1180
 
1181
  first_index = start / BITMAP_ELEMENT_ALL_BITS;
1182
  end_bit_plus1 = start + count;
1183
  last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1184
  elt = bitmap_find_bit (head, start);
1185
 
1186
  /* If bitmap_find_bit returns zero, the current is the closest block
1187
     to the result.  Otherwise, just use bitmap_element_allocate to
1188
     ensure ELT is set; in the loop below, ELT == NULL means "insert
1189
     at the end of the bitmap".  */
1190
  if (!elt)
1191
    {
1192
      elt = bitmap_element_allocate (head);
1193
      elt->indx = first_index;
1194
      bitmap_element_link (head, elt);
1195
    }
1196
 
1197
  gcc_assert (elt->indx == first_index);
1198
  elt_prev = elt->prev;
1199
  for (i = first_index; i <= last_index; i++)
1200
    {
1201
      unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
1202
      unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1203
 
1204
      unsigned int first_word_to_mod;
1205
      BITMAP_WORD first_mask;
1206
      unsigned int last_word_to_mod;
1207
      BITMAP_WORD last_mask;
1208
      unsigned int ix;
1209
 
1210
      if (!elt || elt->indx != i)
1211
        elt = bitmap_elt_insert_after (head, elt_prev, i);
1212
 
1213
      if (elt_start_bit <= start)
1214
        {
1215
          /* The first bit to turn on is somewhere inside this
1216
             elt.  */
1217
          first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1218
 
1219
          /* This mask should have 1s in all bits >= start position. */
1220
          first_mask =
1221
            (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1222
          first_mask = ~first_mask;
1223
        }
1224
      else
1225
        {
1226
          /* The first bit to turn on is below this start of this elt.  */
1227
          first_word_to_mod = 0;
1228
          first_mask = ~(BITMAP_WORD) 0;
1229
        }
1230
 
1231
      if (elt_end_bit_plus1 <= end_bit_plus1)
1232
        {
1233
          /* The last bit to turn on is beyond this elt.  */
1234
          last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1235
          last_mask = ~(BITMAP_WORD) 0;
1236
        }
1237
      else
1238
        {
1239
          /* The last bit to turn on is inside to this elt.  */
1240
          last_word_to_mod =
1241
            (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1242
 
1243
          /* The last mask should have 1s below the end bit.  */
1244
          last_mask =
1245
            (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
1246
        }
1247
 
1248
      if (first_word_to_mod == last_word_to_mod)
1249
        {
1250
          BITMAP_WORD mask = first_mask & last_mask;
1251
          elt->bits[first_word_to_mod] |= mask;
1252
        }
1253
      else
1254
        {
1255
          elt->bits[first_word_to_mod] |= first_mask;
1256
          if (BITMAP_ELEMENT_WORDS > 2)
1257
            for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++)
1258
              elt->bits[ix] = ~(BITMAP_WORD) 0;
1259
          elt->bits[last_word_to_mod] |= last_mask;
1260
        }
1261
 
1262
      elt_prev = elt;
1263
      elt = elt->next;
1264
    }
1265
 
1266
  head->current = elt ? elt : elt_prev;
1267
  head->indx = head->current->indx;
1268
}
1269
 
1270
/* Clear COUNT bits from START in HEAD.  */
1271
void
1272
bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
1273
{
1274
  unsigned int first_index, end_bit_plus1, last_index;
1275
  bitmap_element *elt;
1276
 
1277
  if (!count)
1278
    return;
1279
 
1280
  first_index = start / BITMAP_ELEMENT_ALL_BITS;
1281
  end_bit_plus1 = start + count;
1282
  last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1283
  elt = bitmap_find_bit (head, start);
1284
 
1285
  /* If bitmap_find_bit returns zero, the current is the closest block
1286
     to the result.  If the current is less than first index, find the
1287
     next one.  Otherwise, just set elt to be current.  */
1288
  if (!elt)
1289
    {
1290
      if (head->current)
1291
        {
1292
          if (head->indx < first_index)
1293
            {
1294
              elt = head->current->next;
1295
              if (!elt)
1296
                return;
1297
            }
1298
          else
1299
            elt = head->current;
1300
        }
1301
      else
1302
        return;
1303
    }
1304
 
1305
  while (elt && (elt->indx <= last_index))
1306
    {
1307
      bitmap_element * next_elt = elt->next;
1308
      unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
1309
      unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1310
 
1311
 
1312
      if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
1313
        /* Get rid of the entire elt and go to the next one.  */
1314
        bitmap_element_free (head, elt);
1315
      else
1316
        {
1317
          /* Going to have to knock out some bits in this elt.  */
1318
          unsigned int first_word_to_mod;
1319
          BITMAP_WORD first_mask;
1320
          unsigned int last_word_to_mod;
1321
          BITMAP_WORD last_mask;
1322
          unsigned int i;
1323
          bool clear = true;
1324
 
1325
          if (elt_start_bit <= start)
1326
            {
1327
              /* The first bit to turn off is somewhere inside this
1328
                 elt.  */
1329
              first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1330
 
1331
              /* This mask should have 1s in all bits >= start position. */
1332
              first_mask =
1333
                (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1334
              first_mask = ~first_mask;
1335
            }
1336
          else
1337
            {
1338
              /* The first bit to turn off is below this start of this elt.  */
1339
              first_word_to_mod = 0;
1340
              first_mask = 0;
1341
              first_mask = ~first_mask;
1342
            }
1343
 
1344
          if (elt_end_bit_plus1 <= end_bit_plus1)
1345
            {
1346
              /* The last bit to turn off is beyond this elt.  */
1347
              last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1348
              last_mask = 0;
1349
              last_mask = ~last_mask;
1350
            }
1351
          else
1352
            {
1353
              /* The last bit to turn off is inside to this elt.  */
1354
              last_word_to_mod =
1355
                (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1356
 
1357
              /* The last mask should have 1s below the end bit.  */
1358
              last_mask =
1359
                (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
1360
            }
1361
 
1362
 
1363
          if (first_word_to_mod == last_word_to_mod)
1364
            {
1365
              BITMAP_WORD mask = first_mask & last_mask;
1366
              elt->bits[first_word_to_mod] &= ~mask;
1367
            }
1368
          else
1369
            {
1370
              elt->bits[first_word_to_mod] &= ~first_mask;
1371
              if (BITMAP_ELEMENT_WORDS > 2)
1372
                for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
1373
                  elt->bits[i] = 0;
1374
              elt->bits[last_word_to_mod] &= ~last_mask;
1375
            }
1376
          for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1377
            if (elt->bits[i])
1378
              {
1379
                clear = false;
1380
                break;
1381
              }
1382
          /* Check to see if there are any bits left.  */
1383
          if (clear)
1384
            bitmap_element_free (head, elt);
1385
        }
1386
      elt = next_elt;
1387
    }
1388
 
1389
  if (elt)
1390
    {
1391
      head->current = elt;
1392
      head->indx = head->current->indx;
1393
    }
1394
}
1395
 
1396
/* A = ~A & B. */
1397
 
1398
void
1399
bitmap_compl_and_into (bitmap a, const_bitmap b)
1400
{
1401
  bitmap_element *a_elt = a->first;
1402
  const bitmap_element *b_elt = b->first;
1403
  bitmap_element *a_prev = NULL;
1404
  bitmap_element *next;
1405
 
1406
  gcc_assert (a != b);
1407
 
1408
  if (bitmap_empty_p (a))
1409
    {
1410
      bitmap_copy (a, b);
1411
      return;
1412
    }
1413
  if (bitmap_empty_p (b))
1414
    {
1415
      bitmap_clear (a);
1416
      return;
1417
    }
1418
 
1419
  while (a_elt || b_elt)
1420
    {
1421
      if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1422
        {
1423
          /* A is before B.  Remove A */
1424
          next = a_elt->next;
1425
          a_prev = a_elt->prev;
1426
          bitmap_element_free (a, a_elt);
1427
          a_elt = next;
1428
        }
1429
      else if (!a_elt || b_elt->indx < a_elt->indx)
1430
        {
1431
          /* B is before A.  Copy B. */
1432
          next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1433
          memcpy (next->bits, b_elt->bits, sizeof (next->bits));
1434
          a_prev = next;
1435
          b_elt = b_elt->next;
1436
        }
1437
      else
1438
        {
1439
          /* Matching elts, generate A = ~A & B.  */
1440
          unsigned ix;
1441
          BITMAP_WORD ior = 0;
1442
 
1443
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1444
            {
1445
              BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1446
              BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
1447
 
1448
              a_elt->bits[ix] = r;
1449
              ior |= r;
1450
            }
1451
          next = a_elt->next;
1452
          if (!ior)
1453
            bitmap_element_free (a, a_elt);
1454
          else
1455
            a_prev = a_elt;
1456
          a_elt = next;
1457
          b_elt = b_elt->next;
1458
        }
1459
    }
1460
  gcc_assert (!a->current == !a->first);
1461
  gcc_assert (!a->current || a->indx == a->current->indx);
1462
  return;
1463
}
1464
 
1465
 
1466
/* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1467
   overwriting DST_ELT if non-NULL.  CHANGED is true if the destination bitmap
1468
   had already been changed; the new value of CHANGED is returned.  */
1469
 
1470
static inline bool
1471
bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
1472
                const bitmap_element *a_elt, const bitmap_element *b_elt,
1473
                bool changed)
1474
{
1475
  gcc_assert (a_elt || b_elt);
1476
 
1477
  if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1478
    {
1479
      /* Matching elts, generate A | B.  */
1480
      unsigned ix;
1481
 
1482
      if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1483
        {
1484
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1485
            {
1486
              BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1487
              if (r != dst_elt->bits[ix])
1488
                {
1489
                  dst_elt->bits[ix] = r;
1490
                  changed = true;
1491
                }
1492
            }
1493
        }
1494
      else
1495
        {
1496
          changed = true;
1497
          if (!dst_elt)
1498
            dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1499
          else
1500
            dst_elt->indx = a_elt->indx;
1501
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1502
            {
1503
              BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1504
              dst_elt->bits[ix] = r;
1505
            }
1506
        }
1507
    }
1508
  else
1509
    {
1510
      /* Copy a single element.  */
1511
      const bitmap_element *src;
1512
 
1513
      if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1514
        src = a_elt;
1515
      else
1516
        src = b_elt;
1517
 
1518
      gcc_assert (src);
1519
      changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
1520
    }
1521
  return changed;
1522
}
1523
 
1524
 
1525
/* DST = A | B.  Return true if DST changes.  */
1526
 
1527
bool
1528
bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
1529
{
1530
  bitmap_element *dst_elt = dst->first;
1531
  const bitmap_element *a_elt = a->first;
1532
  const bitmap_element *b_elt = b->first;
1533
  bitmap_element *dst_prev = NULL;
1534
  bitmap_element **dst_prev_pnext = &dst->first;
1535
  bool changed = false;
1536
 
1537
  gcc_assert (dst != a && dst != b);
1538
 
1539
  while (a_elt || b_elt)
1540
    {
1541
      changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
1542
 
1543
      if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1544
        {
1545
          a_elt = a_elt->next;
1546
          b_elt = b_elt->next;
1547
        }
1548
      else
1549
        {
1550
          if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
1551
            a_elt = a_elt->next;
1552
          else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
1553
            b_elt = b_elt->next;
1554
        }
1555
 
1556
      dst_prev = *dst_prev_pnext;
1557
      dst_prev_pnext = &dst_prev->next;
1558
      dst_elt = *dst_prev_pnext;
1559
    }
1560
 
1561
  if (dst_elt)
1562
    {
1563
      changed = true;
1564
      bitmap_elt_clear_from (dst, dst_elt);
1565
    }
1566
  gcc_assert (!dst->current == !dst->first);
1567
  if (dst->current)
1568
    dst->indx = dst->current->indx;
1569
  return changed;
1570
}
1571
 
1572
/* A |= B.  Return true if A changes.  */
1573
 
1574
bool
1575
bitmap_ior_into (bitmap a, const_bitmap b)
1576
{
1577
  bitmap_element *a_elt = a->first;
1578
  const bitmap_element *b_elt = b->first;
1579
  bitmap_element *a_prev = NULL;
1580
  bitmap_element **a_prev_pnext = &a->first;
1581
  bool changed = false;
1582
 
1583
  if (a == b)
1584
    return false;
1585
 
1586
  while (b_elt)
1587
    {
1588
      /* If A lags behind B, just advance it.  */
1589
      if (!a_elt || a_elt->indx == b_elt->indx)
1590
        {
1591
          changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
1592
          b_elt = b_elt->next;
1593
        }
1594
      else if (a_elt->indx > b_elt->indx)
1595
        {
1596
          changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);
1597
          b_elt = b_elt->next;
1598
        }
1599
 
1600
      a_prev = *a_prev_pnext;
1601
      a_prev_pnext = &a_prev->next;
1602
      a_elt = *a_prev_pnext;
1603
    }
1604
 
1605
  gcc_assert (!a->current == !a->first);
1606
  if (a->current)
1607
    a->indx = a->current->indx;
1608
  return changed;
1609
}
1610
 
1611
/* DST = A ^ B  */
1612
 
1613
void
1614
bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b)
1615
{
1616
  bitmap_element *dst_elt = dst->first;
1617
  const bitmap_element *a_elt = a->first;
1618
  const bitmap_element *b_elt = b->first;
1619
  bitmap_element *dst_prev = NULL;
1620
 
1621
  gcc_assert (dst != a && dst != b);
1622
  if (a == b)
1623
    {
1624
      bitmap_clear (dst);
1625
      return;
1626
    }
1627
 
1628
  while (a_elt || b_elt)
1629
    {
1630
      if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1631
        {
1632
          /* Matching elts, generate A ^ B.  */
1633
          unsigned ix;
1634
          BITMAP_WORD ior = 0;
1635
 
1636
          if (!dst_elt)
1637
            dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1638
          else
1639
            dst_elt->indx = a_elt->indx;
1640
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1641
            {
1642
              BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1643
 
1644
              ior |= r;
1645
              dst_elt->bits[ix] = r;
1646
            }
1647
          a_elt = a_elt->next;
1648
          b_elt = b_elt->next;
1649
          if (ior)
1650
            {
1651
              dst_prev = dst_elt;
1652
              dst_elt = dst_elt->next;
1653
            }
1654
        }
1655
      else
1656
        {
1657
          /* Copy a single element.  */
1658
          const bitmap_element *src;
1659
 
1660
          if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1661
            {
1662
              src = a_elt;
1663
              a_elt = a_elt->next;
1664
            }
1665
          else
1666
            {
1667
              src = b_elt;
1668
              b_elt = b_elt->next;
1669
            }
1670
 
1671
          if (!dst_elt)
1672
            dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1673
          else
1674
            dst_elt->indx = src->indx;
1675
          memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1676
          dst_prev = dst_elt;
1677
          dst_elt = dst_elt->next;
1678
        }
1679
    }
1680
  /* Ensure that dst->current is valid.  */
1681
  dst->current = dst->first;
1682
  bitmap_elt_clear_from (dst, dst_elt);
1683
  gcc_assert (!dst->current == !dst->first);
1684
  if (dst->current)
1685
    dst->indx = dst->current->indx;
1686
}
1687
 
1688
/* A ^= B */
1689
 
1690
void
1691
bitmap_xor_into (bitmap a, const_bitmap b)
1692
{
1693
  bitmap_element *a_elt = a->first;
1694
  const bitmap_element *b_elt = b->first;
1695
  bitmap_element *a_prev = NULL;
1696
 
1697
  if (a == b)
1698
    {
1699
      bitmap_clear (a);
1700
      return;
1701
    }
1702
 
1703
  while (b_elt)
1704
    {
1705
      if (!a_elt || b_elt->indx < a_elt->indx)
1706
        {
1707
          /* Copy b_elt.  */
1708
          bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1709
          memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1710
          a_prev = dst;
1711
          b_elt = b_elt->next;
1712
        }
1713
      else if (a_elt->indx < b_elt->indx)
1714
        {
1715
          a_prev = a_elt;
1716
          a_elt = a_elt->next;
1717
        }
1718
      else
1719
        {
1720
          /* Matching elts, generate A ^= B.  */
1721
          unsigned ix;
1722
          BITMAP_WORD ior = 0;
1723
          bitmap_element *next = a_elt->next;
1724
 
1725
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1726
            {
1727
              BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1728
 
1729
              ior |= r;
1730
              a_elt->bits[ix] = r;
1731
            }
1732
          b_elt = b_elt->next;
1733
          if (ior)
1734
            a_prev = a_elt;
1735
          else
1736
            bitmap_element_free (a, a_elt);
1737
          a_elt = next;
1738
        }
1739
    }
1740
  gcc_assert (!a->current == !a->first);
1741
  if (a->current)
1742
    a->indx = a->current->indx;
1743
}
1744
 
1745
/* Return true if two bitmaps are identical.
1746
   We do not bother with a check for pointer equality, as that never
1747
   occurs in practice.  */
1748
 
1749
bool
1750
bitmap_equal_p (const_bitmap a, const_bitmap b)
1751
{
1752
  const bitmap_element *a_elt;
1753
  const bitmap_element *b_elt;
1754
  unsigned ix;
1755
 
1756
  for (a_elt = a->first, b_elt = b->first;
1757
       a_elt && b_elt;
1758
       a_elt = a_elt->next, b_elt = b_elt->next)
1759
    {
1760
      if (a_elt->indx != b_elt->indx)
1761
        return false;
1762
      for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1763
        if (a_elt->bits[ix] != b_elt->bits[ix])
1764
          return false;
1765
    }
1766
  return !a_elt && !b_elt;
1767
}
1768
 
1769
/* Return true if A AND B is not empty.  */
1770
 
1771
bool
1772
bitmap_intersect_p (const_bitmap a, const_bitmap b)
1773
{
1774
  const bitmap_element *a_elt;
1775
  const bitmap_element *b_elt;
1776
  unsigned ix;
1777
 
1778
  for (a_elt = a->first, b_elt = b->first;
1779
       a_elt && b_elt;)
1780
    {
1781
      if (a_elt->indx < b_elt->indx)
1782
        a_elt = a_elt->next;
1783
      else if (b_elt->indx < a_elt->indx)
1784
        b_elt = b_elt->next;
1785
      else
1786
        {
1787
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1788
            if (a_elt->bits[ix] & b_elt->bits[ix])
1789
              return true;
1790
          a_elt = a_elt->next;
1791
          b_elt = b_elt->next;
1792
        }
1793
    }
1794
  return false;
1795
}
1796
 
1797
/* Return true if A AND NOT B is not empty.  */
1798
 
1799
bool
1800
bitmap_intersect_compl_p (const_bitmap a, const_bitmap b)
1801
{
1802
  const bitmap_element *a_elt;
1803
  const bitmap_element *b_elt;
1804
  unsigned ix;
1805
  for (a_elt = a->first, b_elt = b->first;
1806
       a_elt && b_elt;)
1807
    {
1808
      if (a_elt->indx < b_elt->indx)
1809
        return true;
1810
      else if (b_elt->indx < a_elt->indx)
1811
        b_elt = b_elt->next;
1812
      else
1813
        {
1814
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1815
            if (a_elt->bits[ix] & ~b_elt->bits[ix])
1816
              return true;
1817
          a_elt = a_elt->next;
1818
          b_elt = b_elt->next;
1819
        }
1820
    }
1821
  return a_elt != NULL;
1822
}
1823
 
1824
 
1825
/* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
1826
 
1827
bool
1828
bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
1829
{
1830
  bool changed = false;
1831
 
1832
  bitmap_element *dst_elt = dst->first;
1833
  const bitmap_element *a_elt = a->first;
1834
  const bitmap_element *b_elt = b->first;
1835
  const bitmap_element *kill_elt = kill->first;
1836
  bitmap_element *dst_prev = NULL;
1837
  bitmap_element **dst_prev_pnext = &dst->first;
1838
 
1839
  gcc_assert (dst != a && dst != b && dst != kill);
1840
 
1841
  /* Special cases.  We don't bother checking for bitmap_equal_p (b, kill).  */
1842
  if (b == kill || bitmap_empty_p (b))
1843
    {
1844
      changed = !bitmap_equal_p (dst, a);
1845
      if (changed)
1846
        bitmap_copy (dst, a);
1847
      return changed;
1848
    }
1849
  if (bitmap_empty_p (kill))
1850
    return bitmap_ior (dst, a, b);
1851
  if (bitmap_empty_p (a))
1852
    return bitmap_and_compl (dst, b, kill);
1853
 
1854
  while (a_elt || b_elt)
1855
    {
1856
      bool new_element = false;
1857
 
1858
      if (b_elt)
1859
        while (kill_elt && kill_elt->indx < b_elt->indx)
1860
          kill_elt = kill_elt->next;
1861
 
1862
      if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
1863
          && (!a_elt || a_elt->indx >= b_elt->indx))
1864
        {
1865
          bitmap_element tmp_elt;
1866
          unsigned ix;
1867
 
1868
          BITMAP_WORD ior = 0;
1869
          tmp_elt.indx = b_elt->indx;
1870
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1871
            {
1872
              BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
1873
              ior |= r;
1874
              tmp_elt.bits[ix] = r;
1875
            }
1876
 
1877
          if (ior)
1878
            {
1879
              changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
1880
                                        a_elt, &tmp_elt, changed);
1881
              new_element = true;
1882
              if (a_elt && a_elt->indx == b_elt->indx)
1883
                a_elt = a_elt->next;
1884
            }
1885
 
1886
          b_elt = b_elt->next;
1887
          kill_elt = kill_elt->next;
1888
        }
1889
      else
1890
        {
1891
          changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
1892
                                    a_elt, b_elt, changed);
1893
          new_element = true;
1894
 
1895
          if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1896
            {
1897
              a_elt = a_elt->next;
1898
              b_elt = b_elt->next;
1899
            }
1900
          else
1901
            {
1902
              if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
1903
                a_elt = a_elt->next;
1904
              else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
1905
                b_elt = b_elt->next;
1906
            }
1907
        }
1908
 
1909
      if (new_element)
1910
        {
1911
          dst_prev = *dst_prev_pnext;
1912
          dst_prev_pnext = &dst_prev->next;
1913
          dst_elt = *dst_prev_pnext;
1914
        }
1915
    }
1916
 
1917
  if (dst_elt)
1918
    {
1919
      changed = true;
1920
      bitmap_elt_clear_from (dst, dst_elt);
1921
    }
1922
  gcc_assert (!dst->current == !dst->first);
1923
  if (dst->current)
1924
    dst->indx = dst->current->indx;
1925
 
1926
  return changed;
1927
}
1928
 
1929
/* A |= (FROM1 & ~FROM2).  Return true if A changes.  */
1930
 
1931
bool
1932
bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2)
1933
{
1934
  bitmap_head tmp;
1935
  bool changed;
1936
 
1937
  bitmap_initialize (&tmp, &bitmap_default_obstack);
1938
  bitmap_and_compl (&tmp, from1, from2);
1939
  changed = bitmap_ior_into (a, &tmp);
1940
  bitmap_clear (&tmp);
1941
 
1942
  return changed;
1943
}
1944
 
1945
/* A |= (B & C).  Return true if A changes.  */
1946
 
1947
bool
1948
bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
1949
{
1950
  bitmap_element *a_elt = a->first;
1951
  const bitmap_element *b_elt = b->first;
1952
  const bitmap_element *c_elt = c->first;
1953
  bitmap_element and_elt;
1954
  bitmap_element *a_prev = NULL;
1955
  bitmap_element **a_prev_pnext = &a->first;
1956
  bool changed = false;
1957
  unsigned ix;
1958
 
1959
  if (b == c)
1960
    return bitmap_ior_into (a, b);
1961
  if (bitmap_empty_p (b) || bitmap_empty_p (c))
1962
    return false;
1963
 
1964
  and_elt.indx = -1;
1965
  while (b_elt && c_elt)
1966
    {
1967
      BITMAP_WORD overall;
1968
 
1969
      /* Find a common item of B and C.  */
1970
      while (b_elt->indx != c_elt->indx)
1971
        {
1972
          if (b_elt->indx < c_elt->indx)
1973
            {
1974
              b_elt = b_elt->next;
1975
              if (!b_elt)
1976
                goto done;
1977
            }
1978
          else
1979
            {
1980
              c_elt = c_elt->next;
1981
              if (!c_elt)
1982
                goto done;
1983
            }
1984
        }
1985
 
1986
      overall = 0;
1987
      and_elt.indx = b_elt->indx;
1988
      for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1989
        {
1990
          and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
1991
          overall |= and_elt.bits[ix];
1992
        }
1993
 
1994
      b_elt = b_elt->next;
1995
      c_elt = c_elt->next;
1996
      if (!overall)
1997
        continue;
1998
 
1999
      /* Now find a place to insert AND_ELT.  */
2000
      do
2001
        {
2002
          ix = a_elt ? a_elt->indx : and_elt.indx;
2003
          if (ix == and_elt.indx)
2004
            changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
2005
          else if (ix > and_elt.indx)
2006
            changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
2007
 
2008
          a_prev = *a_prev_pnext;
2009
          a_prev_pnext = &a_prev->next;
2010
          a_elt = *a_prev_pnext;
2011
 
2012
          /* If A lagged behind B/C, we advanced it so loop once more.  */
2013
        }
2014
      while (ix < and_elt.indx);
2015
    }
2016
 
2017
 done:
2018
  gcc_assert (!a->current == !a->first);
2019
  if (a->current)
2020
    a->indx = a->current->indx;
2021
  return changed;
2022
}
2023
 
2024
/* Debugging function to print out the contents of a bitmap.  */
2025
 
2026
void
2027
debug_bitmap_file (FILE *file, const_bitmap head)
2028
{
2029
  const bitmap_element *ptr;
2030
 
2031
  fprintf (file, "\nfirst = " HOST_PTR_PRINTF
2032
           " current = " HOST_PTR_PRINTF " indx = %u\n",
2033
           (void *) head->first, (void *) head->current, head->indx);
2034
 
2035
  for (ptr = head->first; ptr; ptr = ptr->next)
2036
    {
2037
      unsigned int i, j, col = 26;
2038
 
2039
      fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
2040
               " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
2041
               (const void*) ptr, (const void*) ptr->next,
2042
               (const void*) ptr->prev, ptr->indx);
2043
 
2044
      for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
2045
        for (j = 0; j < BITMAP_WORD_BITS; j++)
2046
          if ((ptr->bits[i] >> j) & 1)
2047
            {
2048
              if (col > 70)
2049
                {
2050
                  fprintf (file, "\n\t\t\t");
2051
                  col = 24;
2052
                }
2053
 
2054
              fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
2055
                                     + i * BITMAP_WORD_BITS + j));
2056
              col += 4;
2057
            }
2058
 
2059
      fprintf (file, " }\n");
2060
    }
2061
}
2062
 
2063
/* Function to be called from the debugger to print the contents
2064
   of a bitmap.  */
2065
 
2066
void
2067
debug_bitmap (const_bitmap head)
2068
{
2069
  debug_bitmap_file (stdout, head);
2070
}
2071
 
2072
/* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
2073
   it does not print anything but the bits.  */
2074
 
2075
void
2076
bitmap_print (FILE *file, const_bitmap head, const char *prefix, const char *suffix)
2077
{
2078
  const char *comma = "";
2079
  unsigned i;
2080
  bitmap_iterator bi;
2081
 
2082
  fputs (prefix, file);
2083
  EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
2084
    {
2085
      fprintf (file, "%s%d", comma, i);
2086
      comma = ", ";
2087
    }
2088
  fputs (suffix, file);
2089
}
2090
#ifdef GATHER_STATISTICS
2091
 
2092
 
2093
/* Used to accumulate statistics about bitmap sizes.  */
2094
struct output_info
2095
{
2096
  HOST_WIDEST_INT size;
2097
  int count;
2098
};
2099
 
2100
/* Called via htab_traverse.  Output bitmap descriptor pointed out by SLOT
2101
   and update statistics.  */
2102
static int
2103
print_statistics (void **slot, void *b)
2104
{
2105
  struct bitmap_descriptor *d = (struct bitmap_descriptor *) *slot;
2106
  struct output_info *i = (struct output_info *) b;
2107
  char s[4096];
2108
 
2109
  if (d->allocated)
2110
    {
2111
      const char *s1 = d->file;
2112
      const char *s2;
2113
      while ((s2 = strstr (s1, "gcc/")))
2114
        s1 = s2 + 4;
2115
      sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
2116
      s[41] = 0;
2117
      fprintf (stderr, "%-41s %8d %15"HOST_WIDEST_INT_PRINT"d %15"
2118
               HOST_WIDEST_INT_PRINT"d %15"HOST_WIDEST_INT_PRINT"d %10d\n",
2119
               s, d->created, d->allocated, d->peak, d->current, d->nsearches);
2120
      i->size += d->allocated;
2121
      i->count += d->created;
2122
    }
2123
  return 1;
2124
}
2125
#endif
2126
/* Output per-bitmap memory usage statistics.  */
2127
void
2128
dump_bitmap_statistics (void)
2129
{
2130
#ifdef GATHER_STATISTICS
2131
  struct output_info info;
2132
 
2133
  if (!bitmap_desc_hash)
2134
    return;
2135
 
2136
  fprintf (stderr, "\nBitmap                                     Overall "
2137
                   "   Allocated        Peak           Leak   searched "
2138
                   "  per search\n");
2139
  fprintf (stderr, "---------------------------------------------------------------------------------\n");
2140
  info.count = 0;
2141
  info.size = 0;
2142
  htab_traverse (bitmap_desc_hash, print_statistics, &info);
2143
  fprintf (stderr, "---------------------------------------------------------------------------------\n");
2144
  fprintf (stderr, "%-40s %9d %15"HOST_WIDEST_INT_PRINT"d\n",
2145
           "Total", info.count, info.size);
2146
  fprintf (stderr, "---------------------------------------------------------------------------------\n");
2147
#endif
2148
}
2149
 
2150
/* Compute hash of bitmap (for purposes of hashing).  */
2151
hashval_t
2152
bitmap_hash (const_bitmap head)
2153
{
2154
  const bitmap_element *ptr;
2155
  BITMAP_WORD hash = 0;
2156
  int ix;
2157
 
2158
  for (ptr = head->first; ptr; ptr = ptr->next)
2159
    {
2160
      hash ^= ptr->indx;
2161
      for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
2162
        hash ^= ptr->bits[ix];
2163
    }
2164
  return (hashval_t)hash;
2165
}
2166
 
2167
#include "gt-bitmap.h"

powered by: WebSVN 2.1.0

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