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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [ebitmap.c] - Blame information for rev 684

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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