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

Subversion Repositories openrisc

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

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

Line No. Rev Author Line
1 280 jeremybenn
/* Sparse array-based bitmaps.
2
   Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
3
   Contributed by Daniel Berlin <dberlin@dberlin.org>
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 "ebitmap.h"
29
 
30
/* The ebitmap data structure is a sparse bitmap structure that works
31
   by having two pieces:
32
   1. An array of all nonzero words in the structures, organized as
33
   an array of HOST_WIDE_INT's.
34
   2. A non-sparse bitmap saying which bitmap words are present in the
35
   array.
36
 
37
   As a consequence of this representation, testing whether a bit
38
   exists in the bitmap is faster than linked-list bitmaps.  For bits
39
   in words that are all zero, the time to test is O(1).  For bits in
40
   words that exist, it requires O(n/sizeof(word)) time to perform the
41
   test (ignoring the one element cache).  It also has much better
42
   locality than linked-list bitmaps.
43
 
44
   To test whether a bit exists, we do the following:
45
   1. Test whether the word the bit would appear in exists in the
46
   bitmap (O(1) check of the mask).  If not, fail.
47
 
48
   2. Population count the mask up to the word containing the bit, to
49
   find the place in the array the word would be (popcount is cached,
50
   but this is just as slow as the linked-list bitmap)
51
   3. Test the word to see if the bit exists.
52
 
53
   Just like linked-list bitmaps, we cache the last element that has
54
   been tested in order to speed up common access patterns.
55
 
56
   Most of the other speedups are simply due to better locality of the
57
   single contiguous array.
58
 
59
   As would be expected in a structure like this, insertion into an
60
   empty word in the middle requires moving bits to make room for the
61
   new word.   As most operations that perform sets perform them in
62
   order, this is rarely a problem.  We also take advantage of the
63
   same element cache to make repeated sets to the same word O(1).
64
 
65
   Operations on the entire bitmap are also more efficient than linked
66
   list bitmaps, as they are all operating on contiguous memory, and
67
   can be easily vectorized.  They are all O(number of words) +
68
   O(number of bits that may end up in the destination), as the
69
   appropriate operation is first performed on the word mask, and then
70
   only those elements that may generate results are touched.
71
 
72
   Memory wise, the ebitmap starts out using less memory than the
73
   linked-list bitmap, but its size in memory is technically bounded
74
   by ((index of the highest bit set) / (size of a word) + (index of
75
   the highest bit set) / ((size of a word) * (size of a word))) This
76
   is because the mask is non-sparse.  The mask could be transformed
77
   into a sparse bitmap at the cost of making bit testing
78
   *theoretically* slower (real world numbers have not been computed
79
   yet as to whether it matters or not).  */
80
 
81
/* #define EBITMAP_DEBUGGING  */
82
 
83
/* Find the last set bit in ebitmap MAP.  */
84
 
85
int
86
ebitmap_last_set_bit (ebitmap map)
87
{
88
  unsigned int i = 0;
89
  ebitmap_iterator ebi;
90
  bool foundbit = false;
91
 
92
  /* This is not the fastest way to do this, we could simply look for
93
     the popcount, and start there, but this function is not used
94
     anywhere speed critical.  */
95
  EXECUTE_IF_SET_IN_EBITMAP (map, 0, i, ebi)
96
    {
97
      foundbit = true;
98
    }
99
 
100
 
101
  if (foundbit)
102
    return i;
103
  return -1;
104
}
105
 
106
/* Grow or shrink the internal word array for MAP to NEWSIZE
107
   elements.  */
108
 
109
static inline void
110
ebitmap_array_grow (ebitmap map, unsigned int newsize)
111
{
112
  if (newsize <= map->n_elts)
113
    {
114
      map->n_elts = newsize;
115
      return;
116
    }
117
 
118
  newsize += newsize / 4;
119
 
120
  map->n_elts = newsize;
121
  map->elts = XRESIZEVEC (EBITMAP_ELT_TYPE, map->elts, newsize);
122
}
123
 
124
/* Grow the internal word array for MAP so it is at least SIZE
125
   elements.  Will not shrink the array if it is already big
126
   enough.  */
127
 
128
static inline void
129
ebitmap_array_maybe_grow (ebitmap map, unsigned int size)
130
{
131
  if (size >= map->n_elts)
132
    ebitmap_array_grow (map, size + 1);
133
}
134
 
135
/* Retrieve the IDX'th element from the word array for MAP.  */
136
 
137
static inline EBITMAP_ELT_TYPE
138
ebitmap_array_get (ebitmap map, unsigned int idx)
139
{
140
  gcc_assert (idx < map->n_elts);
141
  return map->elts[idx];
142
}
143
 
144
/* Retrieve a pointer to the IDX'th element from the word array for
145
   MAP.  If the element index is greater than the size of the array,
146
   the array will be grown to the correct size.  */
147
 
148
static inline EBITMAP_ELT_TYPE *
149
ebitmap_array_grow_get (ebitmap map, unsigned int idx)
150
{
151
  if (idx >= map->n_elts)
152
    ebitmap_array_grow (map, idx + 1);
153
  return &map->elts[idx];
154
}
155
 
156
/* Initialize the internal word array for MAP, so that it is SIZE
157
   elements.  */
158
 
159
static inline void
160
ebitmap_array_init (ebitmap map, unsigned int size)
161
{
162
  if (size > 0)
163
    {
164
      map->elts = XNEWVEC (EBITMAP_ELT_TYPE, size);
165
      map->n_elts = size;
166
    }
167
  else
168
    {
169
      map->n_elts = 0;
170
      map->elts = NULL;
171
    }
172
}
173
 
174
/* Free the internal word array for MAP.  */
175
 
176
static inline void
177
ebitmap_array_clear (ebitmap map)
178
{
179
  if (map->elts)
180
    {
181
      free (map->elts);
182
      map->elts = NULL;
183
    }
184
  map->n_elts = 0;
185
}
186
 
187
/* Clear ebitmap MAP.  */
188
 
189
void
190
ebitmap_clear (ebitmap map)
191
{
192
  ebitmap_array_clear (map);
193
  sbitmap_zero (map->wordmask);
194
  map->wordmask = sbitmap_resize (map->wordmask, 1, 0);
195
  map->numwords = 0;
196
  map->cache = NULL;
197
  map->cacheindex = 0;
198
}
199
 
200
/* Allocate an ebitmap with enough room for SIZE bits to start out.  */
201
 
202
ebitmap
203
ebitmap_alloc (unsigned int size)
204
{
205
  ebitmap ret = XNEW (struct ebitmap_def);
206
  if (size == 0)
207
    size = EBITMAP_ELT_BITS;
208
  ebitmap_array_init (ret, (size + EBITMAP_ELT_BITS - 1) / EBITMAP_ELT_BITS);
209
  ret->wordmask = sbitmap_alloc_with_popcount (size);
210
  sbitmap_zero (ret->wordmask);
211
  ret->numwords = 0;
212
  ret->cache = NULL;
213
  ret->cacheindex = 0;
214
 
215
  return ret;
216
}
217
 
218
/* Clear BIT from ebitmap MAP.  */
219
 
220
void
221
ebitmap_clear_bit (ebitmap map, unsigned int bit)
222
{
223
  unsigned int wordindex = bit / EBITMAP_ELT_BITS;
224
  unsigned int eltwordindex = 0;
225
  unsigned int bitindex, shift;
226
  bool have_eltwordindex = false;
227
  EBITMAP_ELT_TYPE *elt_ptr;
228
 
229
  /* If the bit can't exist in our bitmap, just return.  */
230
  if (map->numwords == 0)
231
    return;
232
 
233
  if (wordindex >= map->wordmask->n_bits
234
      || !TEST_BIT (map->wordmask, wordindex))
235
    return;
236
 
237
  if (map->cache != NULL && map->cacheindex == wordindex)
238
    elt_ptr = map->cache;
239
  else
240
    {
241
      eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
242
      elt_ptr = &map->elts[eltwordindex];
243
      have_eltwordindex = true;
244
    }
245
 
246
  bitindex = bit % EBITMAP_ELT_BITS;
247
  shift = bitindex;
248
 
249
  *(elt_ptr) &= ~(((EBITMAP_ELT_TYPE)1) << shift);
250
 
251
  /* Clear out the empty words.  */
252
  if (*(elt_ptr) == 0)
253
    {
254
      if (!have_eltwordindex)
255
        eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
256
 
257
      if (map->cache != NULL)
258
        {
259
          if (map->cacheindex == wordindex)
260
            map->cache = NULL;
261
          else if (map->cacheindex > wordindex)
262
            map->cache = map->cache - 1;
263
        }
264
 
265
      RESET_BIT (map->wordmask, wordindex);
266
 
267
      memmove(&map->elts[eltwordindex], &map->elts[eltwordindex + 1],
268
              sizeof (EBITMAP_ELT_TYPE) * (map->numwords - eltwordindex));
269
      map->numwords--;
270
    }
271
}
272
 
273
/* Set BIT in ebitmap MAP.  */
274
 
275
void
276
ebitmap_set_bit (ebitmap map, unsigned int bit)
277
{
278
  unsigned int wordindex = bit / EBITMAP_ELT_BITS;
279
  unsigned int eltwordindex;
280
  unsigned int bitindex =   bit % EBITMAP_ELT_BITS;
281
 
282
  /* If we have this element cached, just set the bit in it.  */
283
  if (map->cache && map->cacheindex == wordindex)
284
    {
285
      (*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex;
286
      return;
287
    }
288
 
289
  /* Resize the wordmask if necessary.  */
290
  if (wordindex >= map->wordmask->n_bits)
291
    map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0);
292
 
293
  /* Allocate a new word in the array and move whatever is in it's
294
     place, if necessary. */
295
  if (!TEST_BIT (map->wordmask, wordindex))
296
    {
297
      unsigned long count;
298
      unsigned int i;
299
 
300
      SET_BIT (map->wordmask, wordindex);
301
      count = sbitmap_popcount (map->wordmask, wordindex);
302
      gcc_assert (count <= map->numwords);
303
 
304
      for (i = map->numwords; i > count; i--)
305
        {
306
          EBITMAP_ELT_TYPE *newelt;
307
          newelt = ebitmap_array_grow_get (map, i);
308
          *newelt = ebitmap_array_get (map, i - 1);
309
        }
310
      map->numwords++;
311
      eltwordindex = count;
312
      ebitmap_array_maybe_grow (map, eltwordindex);
313
      map->elts[eltwordindex] = 0;
314
    }
315
  else
316
    {
317
      eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
318
    }
319
 
320
  /* Set the actual bit.  */
321
  bitindex = bit % EBITMAP_ELT_BITS;
322
 
323
  map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex;
324
  map->cache = &map->elts[eltwordindex];
325
  map->cacheindex = wordindex;
326
}
327
 
328
 
329
/* Return true if MAP contains BIT.  */
330
 
331
bool
332
ebitmap_bit_p (ebitmap map, unsigned int bit)
333
{
334
  unsigned int wordindex = bit / EBITMAP_ELT_BITS;
335
  unsigned int bitindex= bit % EBITMAP_ELT_BITS;
336
 
337
  /* Trivial empty ebitmap case.  */
338
  if (map->numwords == 0)
339
    return false;
340
 
341
  if (map->cache && map->cacheindex == wordindex)
342
    return ((*map->cache) >> bitindex) & 1;
343
 
344
  /* If the wordindex is greater than the size of the wordmask, *or*
345
     it's not set in the wordmask, this bit can't exist in our
346
     ebitmap.  */
347
  if (wordindex >= map->wordmask->n_bits
348
      || !TEST_BIT (map->wordmask, wordindex))
349
    return false;
350
 
351
  /* Find the bit and test it.  */
352
  map->cacheindex = wordindex;
353
  wordindex = sbitmap_popcount (map->wordmask, wordindex);
354
  map->cache = &map->elts[wordindex];
355
 
356
  return (map->elts[wordindex] >> bitindex) & 1;
357
}
358
 
359
/* Copy ebitmap SRC to DST.  */
360
 
361
void
362
ebitmap_copy (ebitmap dst, ebitmap src)
363
{
364
  /* Blow away any existing wordmask, and copy the new one.  */
365
  sbitmap_free (dst->wordmask);
366
  dst->wordmask = sbitmap_alloc_with_popcount (src->wordmask->n_bits);
367
  sbitmap_copy (dst->wordmask, src->wordmask);
368
 
369
  /* Make sure our destination array is big enough, and then copy the
370
     actual words.  */
371
  ebitmap_array_grow (dst, src->numwords);
372
  memcpy (dst->elts, src->elts,
373
          src->numwords * sizeof (EBITMAP_ELT_TYPE));
374
  dst->numwords = src->numwords;
375
  dst->cache = NULL;
376
}
377
 
378
/* Dump ebitmap BMAP to FILE.  */
379
 
380
void
381
dump_ebitmap (FILE *file, ebitmap bmap)
382
{
383
  unsigned int pos;
384
  unsigned int i;
385
  int res;
386
  unsigned int size;
387
 
388
  res = sbitmap_last_set_bit (bmap->wordmask);
389
  if (res == -1)
390
    size = 0;
391
  else
392
    size = (res + 1) * EBITMAP_ELT_BITS;
393
 
394
  fprintf (file, "n_words = %d, set = {", bmap->numwords);
395
 
396
  for (pos = 30, i = 0; i < size; i++)
397
    if (ebitmap_bit_p (bmap, i))
398
      {
399
        if (pos > 70)
400
          {
401
            fprintf (file, "\n  ");
402
            pos = 0;
403
          }
404
 
405
        pos += fprintf (file, "%d ", i);
406
      }
407
 
408
  fprintf (file, "}\n");
409
}
410
 
411
/* Dump ebitmap BMAP to stderr.  */
412
 
413
void
414
debug_ebitmap (ebitmap bmap)
415
{
416
  dump_ebitmap (stderr, bmap);
417
}
418
 
419
/* Perform the operation DST &= SRC.  */
420
 
421
void
422
ebitmap_and_into (ebitmap dst, ebitmap src)
423
{
424
  sbitmap_iterator sbi;
425
  unsigned int i;
426
  unsigned int neweltindex = 0;
427
  unsigned int dsteltindex = 0;
428
  unsigned int srceltindex = 0;
429
 
430
  gcc_assert (dst != src);
431
 
432
  dst->cache = NULL;
433
 
434
  /* Short circuit the empty bitmap cases.  */
435
  if (src->numwords == 0 || dst->numwords == 0)
436
    {
437
      ebitmap_clear (dst);
438
      return;
439
    }
440
 
441
  /* AND the masks, then walk the words that may actually appear in
442
     the result, AND'ing them.  */
443
  sbitmap_a_and_b (dst->wordmask, dst->wordmask, src->wordmask);
444
 
445
  EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
446
    {
447
      EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
448
      tmpword &= ebitmap_array_get (dst, dsteltindex++);
449
      if (tmpword != 0)
450
        {
451
          EBITMAP_ELT_TYPE *dstplace;
452
          dstplace = ebitmap_array_grow_get (dst, neweltindex++);
453
          *dstplace = tmpword;
454
        }
455
      else
456
        RESET_BIT (dst->wordmask, i);
457
    }
458
#ifdef EBITMAP_DEBUGGING
459
  {
460
    unsigned int i;
461
 
462
    for (i = 0; i <  dst->numwords; i++)
463
      gcc_assert (dst->elts[i] != 0);
464
 
465
    sbitmap_verify_popcount (dst->wordmask);
466
    gcc_assert (sbitmap_popcount (dst->wordmask,
467
                                  dst->wordmask->n_bits) == dst->numwords);
468
  }
469
#endif
470
  dst->numwords = neweltindex;
471
}
472
 
473
/* Perform the operation DST = SRC1 & SRC2.  */
474
 
475
void
476
ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2)
477
{
478
  sbitmap_iterator sbi;
479
  unsigned int i;
480
  unsigned int neweltindex = 0;
481
  unsigned int src1eltindex = 0;
482
  unsigned int src2eltindex = 0;
483
 
484
  dst->cache = NULL;
485
  if (src1->numwords == 0 || src2->numwords == 0)
486
    {
487
      ebitmap_clear (dst);
488
      return;
489
    }
490
 
491
  dst->wordmask
492
    = sbitmap_resize (dst->wordmask,
493
                      MIN (src1->wordmask->n_bits, src2->wordmask->n_bits),
494
                      0);
495
  sbitmap_a_and_b (dst->wordmask, src1->wordmask, src2->wordmask);
496
 
497
  EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
498
    {
499
      bool src1hasword, src2hasword;
500
 
501
      src1hasword = TEST_BIT (src1->wordmask, i);
502
      src2hasword = TEST_BIT (src2->wordmask, i);
503
 
504
      if (src1hasword && src2hasword)
505
        {
506
          EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++);
507
          tmpword &= ebitmap_array_get (src2, src2eltindex++);
508
          if (tmpword != 0)
509
            {
510
              EBITMAP_ELT_TYPE *dstplace;
511
              dstplace = ebitmap_array_grow_get (dst, neweltindex++);
512
              *dstplace = tmpword;
513
            }
514
          else
515
            RESET_BIT (dst->wordmask, i);
516
        }
517
      else if (src1hasword)
518
        src1eltindex++;
519
      else
520
        src2eltindex++;
521
    }
522
#ifdef EBITMAP_DEBUGGING
523
  {
524
    ebitmap_iterator ebi;
525
    unsigned int i;
526
 
527
    for (i = 0; i <  dst->numwords; i++)
528
      gcc_assert (dst->elts[i] != 0);
529
 
530
    EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
531
      if (ebitmap_bit_p (src2, i))
532
        gcc_assert (ebitmap_bit_p (dst, i));
533
 
534
    for (i = 0; i <  dst->numwords; i++)
535
      gcc_assert (dst->elts[i] != 0);
536
 
537
    sbitmap_verify_popcount (dst->wordmask);
538
    gcc_assert (sbitmap_popcount (dst->wordmask,
539
                                  dst->wordmask->n_bits) == dst->numwords);
540
  }
541
#endif
542
  dst->numwords = neweltindex;
543
}
544
 
545
/* Perform the operation DST |= SRC.  Return true if any bits in DST
546
   changed.  */
547
 
548
bool
549
ebitmap_ior_into (ebitmap dst, ebitmap src)
550
{
551
  unsigned int dstsize = dst->wordmask->n_bits;
552
  unsigned int srcsize = src->wordmask->n_bits;
553
  sbitmap_iterator sbi;
554
  unsigned int i;
555
  sbitmap tempmask;
556
  unsigned int neweltindex = 0;
557
  unsigned int dsteltindex = 0;
558
  unsigned int srceltindex = 0;
559
  bool changed = false;
560
  EBITMAP_ELT_TYPE *newarray;
561
  unsigned int newarraysize;
562
#ifdef EBITMAP_DEBUGGING
563
  ebitmap dstcopy = ebitmap_alloc (1);
564
  ebitmap_copy (dstcopy, dst);
565
#endif
566
 
567
  dst->cache = NULL;
568
  if (dst == src)
569
    return false;
570
 
571
  if (dst->numwords == 0 && src->numwords != 0)
572
    {
573
      ebitmap_copy (dst, src);
574
      return true;
575
    }
576
  else if (src->numwords == 0)
577
    return false;
578
 
579
  /* We can do without the temp mask if it's faster, but it would mean
580
     touching more words in the actual dense vector.  */
581
  tempmask = sbitmap_alloc (MAX (srcsize, dstsize));
582
  sbitmap_zero (tempmask);
583
  if (srcsize == dstsize)
584
    {
585
      sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask);
586
    }
587
  else
588
    {
589
      dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize),
590
                                      0);
591
      if (srcsize >= dstsize)
592
        {
593
          sbitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size);
594
          sbitmap_a_or_b (tempmask, tempmask, src->wordmask);
595
        }
596
      else
597
        {
598
          sbitmap_copy_n (tempmask, src->wordmask, src->wordmask->size);
599
          sbitmap_a_or_b (tempmask, tempmask, dst->wordmask);
600
        }
601
    }
602
  newarraysize = src->numwords + dst->numwords;
603
  newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
604
 
605
  EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
606
    {
607
      bool dsthasword, srchasword;
608
 
609
      dsthasword = (i < dst->wordmask->n_bits
610
                    && TEST_BIT (dst->wordmask, i));
611
      srchasword = (i < src->wordmask->n_bits
612
                    && TEST_BIT (src->wordmask, i));
613
 
614
      if (dsthasword && srchasword)
615
        {
616
          EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
617
          tmpword |= ebitmap_array_get (dst, dsteltindex);
618
          if (!changed)
619
            changed |= tmpword != ebitmap_array_get (dst, dsteltindex);
620
          dsteltindex++;
621
          newarray[neweltindex++] = tmpword;
622
        }
623
      else if (dsthasword)
624
        {
625
          newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++);
626
        }
627
      else
628
        {
629
          newarray [neweltindex++] = ebitmap_array_get (src, srceltindex++);
630
          gcc_assert (i < dst->wordmask->n_bits);
631
          SET_BIT (dst->wordmask, i);
632
          changed |= true;
633
        }
634
    }
635
 
636
  sbitmap_free (tempmask);
637
  if (changed)
638
    {
639
      dst->numwords = neweltindex;
640
      free (dst->elts);
641
      dst->elts = newarray;
642
      dst->n_elts = newarraysize;
643
    }
644
  else
645
    free (newarray);
646
 
647
#ifdef EBITMAP_DEBUGGING
648
  {
649
    ebitmap_iterator ebi;
650
    unsigned int i;
651
 
652
    for (i = 0; i <  dst->numwords; i++)
653
      gcc_assert (dst->elts[i] != 0);
654
 
655
    EXECUTE_IF_SET_IN_EBITMAP (src, 0, i, ebi)
656
      gcc_assert (ebitmap_bit_p (dst, i));
657
    EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
658
      gcc_assert (ebitmap_bit_p (dst, i));
659
 
660
    sbitmap_verify_popcount (dst->wordmask);
661
    gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
662
    gcc_assert (sbitmap_popcount (dst->wordmask,
663
                                  dst->wordmask->n_bits) == dst->numwords);
664
  }
665
#endif
666
  return changed;
667
}
668
 
669
/* Perform the operation DST = SRC1 | SRC2.  Return true if any bit
670
   in DST has changed.  */
671
 
672
bool
673
ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2)
674
{
675
  unsigned int src1size = src1->wordmask->n_bits;
676
  unsigned int src2size = src2->wordmask->n_bits;
677
  sbitmap_iterator sbi;
678
  unsigned int i;
679
  sbitmap tempmask;
680
  unsigned int neweltindex = 0;
681
  unsigned int src1eltindex = 0;
682
  unsigned int src2eltindex = 0;
683
  bool changed = false;
684
  EBITMAP_ELT_TYPE *newarray;
685
  unsigned int newarraysize;
686
#ifdef EBITMAP_DEBUGGING
687
  ebitmap dstcopy = ebitmap_alloc (1);
688
  ebitmap_copy (dstcopy, dst);
689
#endif
690
 
691
  dst->cache = NULL;
692
  tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size));
693
  sbitmap_zero (tempmask);
694
  if (src1size == src2size)
695
    {
696
      sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask);
697
    }
698
  else
699
    {
700
      if (src1size >= src2size)
701
        {
702
          sbitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size);
703
          sbitmap_a_or_b (tempmask, tempmask, src1->wordmask);
704
        }
705
      else
706
        {
707
          sbitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size);
708
          sbitmap_a_or_b (tempmask, tempmask, src2->wordmask);
709
        }
710
    }
711
  newarraysize = src1->numwords + src2->numwords;
712
  newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
713
 
714
  EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
715
    {
716
      bool src1hasword, src2hasword;
717
      EBITMAP_ELT_TYPE tmpword;
718
      src1hasword = (i < src1->wordmask->n_bits
719
                    && TEST_BIT (src1->wordmask, i));
720
      src2hasword = (i < src2->wordmask->n_bits
721
                    && TEST_BIT (src2->wordmask, i));
722
 
723
      if (src1hasword && src2hasword)
724
        {
725
          tmpword = (ebitmap_array_get (src1, src1eltindex++)
726
                     | ebitmap_array_get (src2, src2eltindex++));
727
          newarray[neweltindex++] = tmpword;
728
        }
729
      else if (src1hasword)
730
        {
731
          tmpword = ebitmap_array_get (src1, src1eltindex++);
732
          newarray [neweltindex++] = tmpword;
733
        }
734
      else
735
        {
736
          tmpword = ebitmap_array_get (src2, src2eltindex++);
737
          newarray [neweltindex++] = tmpword;
738
        }
739
 
740
      if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
741
        {
742
          changed = true;
743
        }
744
      else if (!changed)
745
        {
746
          unsigned int count = sbitmap_popcount (dst->wordmask, i);
747
          changed |= ebitmap_array_get (dst, count) != tmpword;
748
        }
749
    }
750
 
751
  if (changed)
752
    {
753
      sbitmap_free (dst->wordmask);
754
      dst->wordmask = tempmask;
755
      dst->numwords = neweltindex;
756
      free (dst->elts);
757
      dst->elts = newarray;
758
      dst->n_elts = newarraysize;
759
    }
760
  else
761
    {
762
      sbitmap_free (tempmask);
763
      free (newarray);
764
    }
765
 
766
#ifdef EBITMAP_DEBUGGING
767
  {
768
    ebitmap_iterator ebi;
769
    unsigned int i;
770
 
771
    for (i = 0; i <  dst->numwords; i++)
772
      gcc_assert (dst->elts[i] != 0);
773
 
774
    EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
775
      gcc_assert (ebitmap_bit_p (dst, i));
776
 
777
    EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi)
778
      gcc_assert (ebitmap_bit_p (dst, i));
779
  }
780
  sbitmap_verify_popcount (dst->wordmask);
781
  gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
782
  gcc_assert (sbitmap_popcount (dst->wordmask,
783
                                dst->wordmask->n_bits) == dst->numwords);
784
#endif
785
 
786
  return changed;
787
}
788
 
789
/* Perform the operation DST &= ~SRC.  Return true if any bit in DST
790
   has changed.  */
791
 
792
bool
793
ebitmap_and_compl_into (ebitmap dst, ebitmap src)
794
{
795
  bool changed = false;
796
  unsigned int i;
797
  unsigned int neweltindex = 0;
798
  unsigned int dsteltindex = 0;
799
  sbitmap_iterator sbi;
800
#ifdef EBITMAP_DEBUGGING
801
  ebitmap dstcopy = ebitmap_alloc (1);
802
  ebitmap_copy (dstcopy, dst);
803
#endif
804
 
805
  gcc_assert (dst != src);
806
  dst->cache = NULL;
807
  if (src->numwords == 0)
808
    return false;
809
 
810
  EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
811
    {
812
      bool srchasword;
813
 
814
      srchasword = (i < src->wordmask->n_bits
815
                    && TEST_BIT (src->wordmask, i));
816
 
817
      if (srchasword)
818
        {
819
          unsigned int srccount = sbitmap_popcount (src->wordmask, i);
820
          EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex);
821
          tmpword &= ~(ebitmap_array_get (src, srccount));
822
          if (!changed)
823
            changed |= ebitmap_array_get (dst, dsteltindex) != tmpword;
824
          dsteltindex++;
825
          if (tmpword != 0)
826
            {
827
              EBITMAP_ELT_TYPE *dstplace;
828
              dstplace = ebitmap_array_grow_get (dst, neweltindex++);
829
              *dstplace = tmpword;
830
            }
831
          else
832
            RESET_BIT (dst->wordmask, i);
833
        }
834
      else
835
        {
836
          dsteltindex++;
837
          neweltindex++;
838
        }
839
    }
840
#ifdef EBITMAP_DEBUGGING
841
  {
842
    unsigned int i;
843
    ebitmap_iterator ebi;
844
 
845
    EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
846
      {
847
        if (!ebitmap_bit_p (src, i))
848
          gcc_assert (ebitmap_bit_p (dst, i));
849
      }
850
 
851
    for (i = 0; i <  dst->numwords; i++)
852
      gcc_assert (dst->elts[i] != 0);
853
 
854
    gcc_assert (sbitmap_popcount (dst->wordmask,
855
                                  dst->wordmask->n_bits) == neweltindex);
856
    sbitmap_verify_popcount (dst->wordmask);
857
    gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
858
    gcc_assert (sbitmap_popcount (dst->wordmask,
859
                                  dst->wordmask->n_bits) == dst->numwords);
860
  }
861
#endif
862
  dst->numwords = neweltindex;
863
  /* sbitmap_popcount (dst->wordmask, -1); */
864
 
865
  return changed;
866
}
867
 
868
/* Perform the operation DST = SRC1 & ~SRC2.  Return true if any bit
869
   in DST has changed.  */
870
 
871
bool
872
ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2)
873
{
874
  unsigned int src1size = src1->wordmask->n_bits;
875
  sbitmap_iterator sbi;
876
  unsigned int i;
877
  sbitmap tempmask;
878
  unsigned int neweltindex = 0;
879
  unsigned int src1eltindex = 0;
880
  bool changed = false;
881
  EBITMAP_ELT_TYPE *newarray;
882
  unsigned int newarraysize;
883
 
884
  /* XXX: Optimize like the into version.  */
885
  dst->cache = NULL;
886
  tempmask = sbitmap_alloc_with_popcount (src1size);
887
  sbitmap_zero (tempmask);
888
  sbitmap_copy (tempmask, src1->wordmask);
889
 
890
  newarraysize = src1->numwords;
891
  newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
892
 
893
  EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi)
894
    {
895
      bool src2hasword;
896
      EBITMAP_ELT_TYPE tmpword;
897
 
898
      src2hasword = (i < src2->wordmask->n_bits
899
                     && TEST_BIT (src2->wordmask, i));
900
 
901
      if (src2hasword)
902
        {
903
          unsigned int src2count = sbitmap_popcount (src2->wordmask, i);
904
          tmpword = ebitmap_array_get (src1, src1eltindex++)
905
                    & ~(ebitmap_array_get (src2, src2count));
906
          if (tmpword)
907
            {
908
              newarray[neweltindex++] = tmpword;
909
            }
910
          else
911
            RESET_BIT (tempmask, i);
912
 
913
        }
914
      else
915
        {
916
          tmpword = ebitmap_array_get (src1, src1eltindex++);
917
          gcc_assert (tmpword != 0);
918
          newarray[neweltindex++] = tmpword;
919
        }
920
 
921
      if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
922
        {
923
          changed = true;
924
        }
925
      else if (!changed)
926
        {
927
          unsigned int count = sbitmap_popcount (dst->wordmask, i);
928
          changed |= ebitmap_array_get (dst, count) != tmpword;
929
        }
930
    }
931
  if (changed)
932
    {
933
      sbitmap_free (dst->wordmask);
934
      dst->wordmask = tempmask;
935
      dst->numwords = neweltindex;
936
      free (dst->elts);
937
      dst->elts = newarray;
938
      dst->n_elts = newarraysize;
939
    }
940
  else
941
    {
942
      free (tempmask);
943
      free (newarray);
944
    }
945
#ifdef EBITMAP_DEBUGGING
946
  {
947
    unsigned int i;
948
    ebitmap_iterator ebi;
949
 
950
    EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
951
      {
952
        if (!ebitmap_bit_p (src2, i))
953
          gcc_assert (ebitmap_bit_p (dst, i));
954
      }
955
  for (i = 0; i <  dst->numwords; i++)
956
    gcc_assert (dst->elts[i] != 0);
957
 
958
  sbitmap_verify_popcount (dst->wordmask);
959
  gcc_assert (sbitmap_popcount (dst->wordmask,
960
                                dst->wordmask->n_bits) == dst->numwords);
961
  }
962
#endif
963
  return changed;
964
}
965
 
966
/* Perform the operation DST = A | (B & ~C).  */
967
 
968
bool
969
ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c)
970
{
971
  bool changed;
972
  ebitmap temp = ebitmap_alloc (1);
973
#ifdef EBITMAP_DEBUGGING
974
  ebitmap dstcopy = ebitmap_alloc (1);
975
  ebitmap_copy (dstcopy, dst);
976
#endif
977
 
978
  dst->cache = NULL;
979
  ebitmap_and_compl (temp, b, c);
980
  changed = ebitmap_ior (dst, a, temp);
981
#ifdef EBITMAP_DEBUGGING
982
  {
983
    ebitmap_iterator ebi;
984
    unsigned int i;
985
 
986
    EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi)
987
      gcc_assert (ebitmap_bit_p (dst, i));
988
 
989
    EXECUTE_IF_SET_IN_EBITMAP (b, 0, i, ebi)
990
      if (!ebitmap_bit_p (c, i))
991
        gcc_assert (ebitmap_bit_p (dst, i));
992
    gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
993
  }
994
#endif
995
  ebitmap_free (temp);
996
 
997
  return changed;
998
}
999
 
1000
/* Return true if ebitmap DST is equal to ebitmap SRC.  */
1001
 
1002
bool
1003
ebitmap_equal_p (ebitmap dst, ebitmap src)
1004
{
1005
  unsigned int which = MIN (dst->wordmask->size, src->wordmask->size);
1006
 
1007
  if (dst->numwords != src->numwords)
1008
    return false;
1009
 
1010
  /* sbitmap_equal compares up to the size of the first argument, so
1011
     if the two sbitmaps are not equally sized, we need to pass the
1012
     smaller one as the first argument, or it will crash.  */
1013
  if (which == dst->wordmask->size
1014
      && !sbitmap_equal (dst->wordmask, src->wordmask))
1015
    return false;
1016
  else if (which == src->wordmask->size
1017
           && !sbitmap_equal (src->wordmask, dst->wordmask))
1018
    return false;
1019
 
1020
  return memcmp (dst->elts, src->elts,
1021
                 dst->numwords * sizeof (EBITMAP_ELT_TYPE)) == 0;
1022
  return true;
1023
}

powered by: WebSVN 2.1.0

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