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

Subversion Repositories openrisc_me

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

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Simple bitmaps.
2
   Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007, 2008
3
   Free Software Foundation, Inc.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "rtl.h"
26
#include "flags.h"
27
#include "hard-reg-set.h"
28
#include "obstack.h"
29
#include "basic-block.h"
30
 
31
#if GCC_VERSION >= 3400
32
#if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
33
#define do_popcount(x) __builtin_popcountl(x)
34
#elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG
35
#define do_popcount(x) __builtin_popcountll(x)
36
#else
37
#error "internal error: sbitmap.h and hwint.h are inconsistent"
38
#endif
39
#else
40
static unsigned long sbitmap_elt_popcount (SBITMAP_ELT_TYPE);
41
#define do_popcount(x) sbitmap_elt_popcount((x))
42
#endif
43
 
44
/* This macro controls debugging that is as expensive as the
45
   operations it verifies.  */
46
 
47
/* #define BITMAP_DEBUGGING  */
48
#ifdef BITMAP_DEBUGGING
49
 
50
/* Verify the population count of sbitmap A matches the cached value,
51
   if there is a cached value. */
52
 
53
void
54
sbitmap_verify_popcount (const_sbitmap a)
55
{
56
  unsigned ix;
57
  unsigned int lastword;
58
 
59
  if (!a->popcount)
60
    return;
61
 
62
  lastword = a->size;
63
  for (ix = 0; ix < lastword; ix++)
64
    gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
65
}
66
#endif
67
 
68
/* Bitmap manipulation routines.  */
69
 
70
/* Allocate a simple bitmap of N_ELMS bits.  */
71
 
72
sbitmap
73
sbitmap_alloc (unsigned int n_elms)
74
{
75
  unsigned int bytes, size, amt;
76
  sbitmap bmap;
77
 
78
  size = SBITMAP_SET_SIZE (n_elms);
79
  bytes = size * sizeof (SBITMAP_ELT_TYPE);
80
  amt = (sizeof (struct simple_bitmap_def)
81
         + bytes - sizeof (SBITMAP_ELT_TYPE));
82
  bmap = (sbitmap) xmalloc (amt);
83
  bmap->n_bits = n_elms;
84
  bmap->size = size;
85
  bmap->popcount = NULL;
86
  return bmap;
87
}
88
 
89
/* Allocate a simple bitmap of N_ELMS bits, and a popcount array.  */
90
 
91
sbitmap
92
sbitmap_alloc_with_popcount (unsigned int n_elms)
93
{
94
  sbitmap const bmap = sbitmap_alloc (n_elms);
95
  bmap->popcount = XNEWVEC (unsigned char, bmap->size);
96
  return bmap;
97
}
98
 
99
/* Resize a simple bitmap BMAP to N_ELMS bits.  If increasing the
100
   size of BMAP, clear the new bits to zero if the DEF argument
101
   is zero, and set them to one otherwise.  */
102
 
103
sbitmap
104
sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
105
{
106
  unsigned int bytes, size, amt;
107
  unsigned int last_bit;
108
 
109
  size = SBITMAP_SET_SIZE (n_elms);
110
  bytes = size * sizeof (SBITMAP_ELT_TYPE);
111
  if (bytes > SBITMAP_SIZE_BYTES (bmap))
112
    {
113
      amt = (sizeof (struct simple_bitmap_def)
114
            + bytes - sizeof (SBITMAP_ELT_TYPE));
115
      bmap = (sbitmap) xrealloc (bmap, amt);
116
      if (bmap->popcount)
117
        bmap->popcount = XRESIZEVEC (unsigned char, bmap->popcount, size);
118
    }
119
 
120
  if (n_elms > bmap->n_bits)
121
    {
122
      if (def)
123
        {
124
          memset (bmap->elms + bmap->size, -1,
125
                  bytes - SBITMAP_SIZE_BYTES (bmap));
126
 
127
          /* Set the new bits if the original last element.  */
128
          last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
129
          if (last_bit)
130
            bmap->elms[bmap->size - 1]
131
              |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
132
 
133
          /* Clear the unused bit in the new last element.  */
134
          last_bit = n_elms % SBITMAP_ELT_BITS;
135
          if (last_bit)
136
            bmap->elms[size - 1]
137
              &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
138
        }
139
      else
140
        {
141
          memset (bmap->elms + bmap->size, 0,
142
                  bytes - SBITMAP_SIZE_BYTES (bmap));
143
          if (bmap->popcount)
144
            memset (bmap->popcount + bmap->size, 0,
145
                    (size * sizeof (unsigned char))
146
                    - (bmap->size * sizeof (unsigned char)));
147
 
148
        }
149
    }
150
  else if (n_elms < bmap->n_bits)
151
    {
152
      /* Clear the surplus bits in the last word.  */
153
      last_bit = n_elms % SBITMAP_ELT_BITS;
154
      if (last_bit)
155
        {
156
          bmap->elms[size - 1]
157
            &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
158
          if (bmap->popcount)
159
            bmap->popcount[size - 1] = do_popcount (bmap->elms[size - 1]);
160
        }
161
    }
162
 
163
  bmap->n_bits = n_elms;
164
  bmap->size = size;
165
  return bmap;
166
}
167
 
168
/* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized.  */
169
 
170
sbitmap
171
sbitmap_realloc (sbitmap src, unsigned int n_elms)
172
{
173
  unsigned int bytes, size, amt;
174
  sbitmap bmap;
175
 
176
  size = SBITMAP_SET_SIZE (n_elms);
177
  bytes = size * sizeof (SBITMAP_ELT_TYPE);
178
  amt = (sizeof (struct simple_bitmap_def)
179
         + bytes - sizeof (SBITMAP_ELT_TYPE));
180
 
181
  if (SBITMAP_SIZE_BYTES (src)  >= bytes)
182
    {
183
      src->n_bits = n_elms;
184
      return src;
185
    }
186
 
187
  bmap = (sbitmap) xrealloc (src, amt);
188
  bmap->n_bits = n_elms;
189
  bmap->size = size;
190
  return bmap;
191
}
192
 
193
/* Allocate a vector of N_VECS bitmaps of N_ELMS bits.  */
194
 
195
sbitmap *
196
sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
197
{
198
  unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
199
  sbitmap *bitmap_vector;
200
 
201
  size = SBITMAP_SET_SIZE (n_elms);
202
  bytes = size * sizeof (SBITMAP_ELT_TYPE);
203
  elm_bytes = (sizeof (struct simple_bitmap_def)
204
               + bytes - sizeof (SBITMAP_ELT_TYPE));
205
  vector_bytes = n_vecs * sizeof (sbitmap *);
206
 
207
  /* Round up `vector_bytes' to account for the alignment requirements
208
     of an sbitmap.  One could allocate the vector-table and set of sbitmaps
209
     separately, but that requires maintaining two pointers or creating
210
     a cover struct to hold both pointers (so our result is still just
211
     one pointer).  Neither is a bad idea, but this is simpler for now.  */
212
  {
213
    /* Based on DEFAULT_ALIGNMENT computation in obstack.c.  */
214
    struct { char x; SBITMAP_ELT_TYPE y; } align;
215
    int alignment = (char *) & align.y - & align.x;
216
    vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
217
  }
218
 
219
  amt = vector_bytes + (n_vecs * elm_bytes);
220
  bitmap_vector = (sbitmap *) xmalloc (amt);
221
 
222
  for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
223
    {
224
      sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
225
 
226
      bitmap_vector[i] = b;
227
      b->n_bits = n_elms;
228
      b->size = size;
229
      b->popcount = NULL;
230
    }
231
 
232
  return bitmap_vector;
233
}
234
 
235
/* Copy sbitmap SRC to DST.  */
236
 
237
void
238
sbitmap_copy (sbitmap dst, const_sbitmap src)
239
{
240
  memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
241
  if (dst->popcount)
242
    memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * dst->size);
243
}
244
 
245
/* Copy the first N elements of sbitmap SRC to DST.  */
246
 
247
void
248
sbitmap_copy_n (sbitmap dst, const_sbitmap src, unsigned int n)
249
{
250
  memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n);
251
  if (dst->popcount)
252
    memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * n);
253
}
254
 
255
/* Determine if a == b.  */
256
int
257
sbitmap_equal (const_sbitmap a, const_sbitmap b)
258
{
259
  return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
260
}
261
 
262
/* Return true if the bitmap is empty.  */
263
 
264
bool
265
sbitmap_empty_p (const_sbitmap bmap)
266
{
267
  unsigned int i;
268
  for (i=0; i<bmap->size; i++)
269
    if (bmap->elms[i])
270
      return false;
271
 
272
  return true;
273
}
274
 
275
/* Return false if any of the N bits are set in MAP starting at
276
   START.  */
277
 
278
bool
279
sbitmap_range_empty_p (const_sbitmap bmap, unsigned int start, unsigned int n)
280
{
281
  unsigned int i = start / SBITMAP_ELT_BITS;
282
  SBITMAP_ELT_TYPE elm;
283
  unsigned int shift = start % SBITMAP_ELT_BITS;
284
 
285
  gcc_assert (bmap->n_bits >= start + n);
286
 
287
  elm = bmap->elms[i];
288
  elm = elm >> shift;
289
 
290
  if (shift + n <= SBITMAP_ELT_BITS)
291
    {
292
      /* The bits are totally contained in a single element.  */
293
      if (shift + n < SBITMAP_ELT_BITS)
294
        elm &= ((1 << n) - 1);
295
      return (elm == 0);
296
    }
297
 
298
  if (elm)
299
    return false;
300
 
301
  n -= SBITMAP_ELT_BITS - shift;
302
  i++;
303
 
304
  /* Deal with full elts.  */
305
  while (n >= SBITMAP_ELT_BITS)
306
    {
307
      if (bmap->elms[i])
308
        return false;
309
      i++;
310
      n -= SBITMAP_ELT_BITS;
311
    }
312
 
313
  /* The leftover bits.  */
314
  if (n)
315
    {
316
      elm = bmap->elms[i];
317
      elm &= ((1 << n) - 1);
318
      return (elm == 0);
319
    }
320
 
321
  return true;
322
}
323
 
324
 
325
 
326
/* Zero all elements in a bitmap.  */
327
 
328
void
329
sbitmap_zero (sbitmap bmap)
330
{
331
  memset (bmap->elms, 0, SBITMAP_SIZE_BYTES (bmap));
332
  if (bmap->popcount)
333
    memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char));
334
}
335
 
336
/* Set all elements in a bitmap to ones.  */
337
 
338
void
339
sbitmap_ones (sbitmap bmap)
340
{
341
  unsigned int last_bit;
342
 
343
  memset (bmap->elms, -1, SBITMAP_SIZE_BYTES (bmap));
344
  if (bmap->popcount)
345
    memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char));
346
 
347
  last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
348
  if (last_bit)
349
    {
350
      bmap->elms[bmap->size - 1]
351
        = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
352
      if (bmap->popcount)
353
        bmap->popcount[bmap->size - 1]
354
          = do_popcount (bmap->elms[bmap->size - 1]);
355
    }
356
}
357
 
358
/* Zero a vector of N_VECS bitmaps.  */
359
 
360
void
361
sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs)
362
{
363
  unsigned int i;
364
 
365
  for (i = 0; i < n_vecs; i++)
366
    sbitmap_zero (bmap[i]);
367
}
368
 
369
/* Set a vector of N_VECS bitmaps to ones.  */
370
 
371
void
372
sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
373
{
374
  unsigned int i;
375
 
376
  for (i = 0; i < n_vecs; i++)
377
    sbitmap_ones (bmap[i]);
378
}
379
 
380
/* Set DST to be A union (B - C).
381
   DST = A | (B & ~C).
382
   Returns true if any change is made.  */
383
 
384
bool
385
sbitmap_union_of_diff_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
386
{
387
  unsigned int i, n = dst->size;
388
  sbitmap_ptr dstp = dst->elms;
389
  const_sbitmap_ptr ap = a->elms;
390
  const_sbitmap_ptr bp = b->elms;
391
  const_sbitmap_ptr cp = c->elms;
392
  SBITMAP_ELT_TYPE changed = 0;
393
 
394
  gcc_assert (!dst->popcount);
395
 
396
  for (i = 0; i < n; i++)
397
    {
398
      const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
399
      changed |= *dstp ^ tmp;
400
      *dstp++ = tmp;
401
    }
402
 
403
  return changed != 0;
404
}
405
 
406
void
407
sbitmap_union_of_diff (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
408
{
409
  unsigned int i, n = dst->size;
410
  sbitmap_ptr dstp = dst->elms;
411
  const_sbitmap_ptr ap = a->elms;
412
  const_sbitmap_ptr bp = b->elms;
413
  const_sbitmap_ptr cp = c->elms;
414
 
415
  gcc_assert (!dst->popcount && !a->popcount
416
              && !b->popcount && !c->popcount);
417
 
418
  for (i = 0; i < n; i++)
419
    *dstp++ = *ap++ | (*bp++ & ~*cp++);
420
}
421
 
422
/* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
423
 
424
void
425
sbitmap_not (sbitmap dst, const_sbitmap src)
426
{
427
  unsigned int i, n = dst->size;
428
  sbitmap_ptr dstp = dst->elms;
429
  const_sbitmap_ptr srcp = src->elms;
430
  unsigned int last_bit;
431
 
432
  gcc_assert (!dst->popcount);
433
 
434
  for (i = 0; i < n; i++)
435
    *dstp++ = ~*srcp++;
436
 
437
  /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones.  */
438
  last_bit = src->n_bits % SBITMAP_ELT_BITS;
439
  if (last_bit)
440
    dst->elms[n-1] = dst->elms[n-1]
441
      & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
442
}
443
 
444
/* Set the bits in DST to be the difference between the bits
445
   in A and the bits in B. i.e. dst = a & (~b).  */
446
 
447
void
448
sbitmap_difference (sbitmap dst, const_sbitmap a, const_sbitmap b)
449
{
450
  unsigned int i, dst_size = dst->size;
451
  unsigned int min_size = dst->size;
452
  sbitmap_ptr dstp = dst->elms;
453
  const_sbitmap_ptr ap = a->elms;
454
  const_sbitmap_ptr bp = b->elms;
455
 
456
  gcc_assert (!dst->popcount);
457
 
458
  /* A should be at least as large as DEST, to have a defined source.  */
459
  gcc_assert (a->size >= dst_size);
460
  /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
461
     only copy the subtrahend into dest.  */
462
  if (b->size < min_size)
463
    min_size = b->size;
464
  for (i = 0; i < min_size; i++)
465
    *dstp++ = *ap++ & (~*bp++);
466
  /* Now fill the rest of dest from A, if B was too short.
467
     This makes sense only when destination and A differ.  */
468
  if (dst != a && i != dst_size)
469
    for (; i < dst_size; i++)
470
      *dstp++ = *ap++;
471
}
472
 
473
/* Return true if there are any bits set in A are also set in B.
474
   Return false otherwise.  */
475
 
476
bool
477
sbitmap_any_common_bits (const_sbitmap a, const_sbitmap b)
478
{
479
  const_sbitmap_ptr ap = a->elms;
480
  const_sbitmap_ptr bp = b->elms;
481
  unsigned int i, n;
482
 
483
  n = MIN (a->size, b->size);
484
  for (i = 0; i < n; i++)
485
    if ((*ap++ & *bp++) != 0)
486
      return true;
487
 
488
  return false;
489
}
490
 
491
/* Set DST to be (A and B).
492
   Return nonzero if any change is made.  */
493
 
494
bool
495
sbitmap_a_and_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
496
{
497
  unsigned int i, n = dst->size;
498
  sbitmap_ptr dstp = dst->elms;
499
  const_sbitmap_ptr ap = a->elms;
500
  const_sbitmap_ptr bp = b->elms;
501
  SBITMAP_ELT_TYPE changed = 0;
502
 
503
  gcc_assert (!dst->popcount);
504
 
505
  for (i = 0; i < n; i++)
506
    {
507
      const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
508
      changed |= *dstp ^ tmp;
509
      *dstp++ = tmp;
510
    }
511
 
512
  return changed != 0;
513
}
514
 
515
void
516
sbitmap_a_and_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
517
{
518
  unsigned int i, n = dst->size;
519
  sbitmap_ptr dstp = dst->elms;
520
  const_sbitmap_ptr ap = a->elms;
521
  const_sbitmap_ptr bp = b->elms;
522
  bool has_popcount = dst->popcount != NULL;
523
  unsigned char *popcountp = dst->popcount;
524
 
525
  for (i = 0; i < n; i++)
526
    {
527
      const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
528
      if (has_popcount)
529
        {
530
          bool wordchanged = (*dstp ^ tmp) != 0;
531
          if (wordchanged)
532
            *popcountp = do_popcount (tmp);
533
          popcountp++;
534
        }
535
      *dstp++ = tmp;
536
    }
537
#ifdef BITMAP_DEBUGGING
538
  if (has_popcount)
539
    sbitmap_verify_popcount (dst);
540
#endif
541
}
542
 
543
/* Set DST to be (A xor B)).
544
   Return nonzero if any change is made.  */
545
 
546
bool
547
sbitmap_a_xor_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
548
{
549
  unsigned int i, n = dst->size;
550
  sbitmap_ptr dstp = dst->elms;
551
  const_sbitmap_ptr ap = a->elms;
552
  const_sbitmap_ptr bp = b->elms;
553
  SBITMAP_ELT_TYPE changed = 0;
554
 
555
  gcc_assert (!dst->popcount);
556
 
557
  for (i = 0; i < n; i++)
558
    {
559
      const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
560
      changed |= *dstp ^ tmp;
561
      *dstp++ = tmp;
562
    }
563
 
564
  return changed != 0;
565
}
566
 
567
void
568
sbitmap_a_xor_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
569
{
570
  unsigned int i, n = dst->size;
571
  sbitmap_ptr dstp = dst->elms;
572
  const_sbitmap_ptr ap = a->elms;
573
  const_sbitmap_ptr bp = b->elms;
574
  bool has_popcount = dst->popcount != NULL;
575
  unsigned char *popcountp = dst->popcount;
576
 
577
  for (i = 0; i < n; i++)
578
    {
579
      const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
580
      if (has_popcount)
581
        {
582
          bool wordchanged = (*dstp ^ tmp) != 0;
583
          if (wordchanged)
584
            *popcountp = do_popcount (tmp);
585
          popcountp++;
586
        }
587
      *dstp++ = tmp;
588
    }
589
#ifdef BITMAP_DEBUGGING
590
  if (has_popcount)
591
    sbitmap_verify_popcount (dst);
592
#endif
593
}
594
 
595
/* Set DST to be (A or B)).
596
   Return nonzero if any change is made.  */
597
 
598
bool
599
sbitmap_a_or_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
600
{
601
  unsigned int i, n = dst->size;
602
  sbitmap_ptr dstp = dst->elms;
603
  const_sbitmap_ptr ap = a->elms;
604
  const_sbitmap_ptr bp = b->elms;
605
  SBITMAP_ELT_TYPE changed = 0;
606
 
607
  gcc_assert (!dst->popcount);
608
 
609
  for (i = 0; i < n; i++)
610
    {
611
      const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
612
      changed |= *dstp ^ tmp;
613
      *dstp++ = tmp;
614
    }
615
 
616
  return changed != 0;
617
}
618
 
619
void
620
sbitmap_a_or_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
621
{
622
  unsigned int i, n = dst->size;
623
  sbitmap_ptr dstp = dst->elms;
624
  const_sbitmap_ptr ap = a->elms;
625
  const_sbitmap_ptr bp = b->elms;
626
  bool has_popcount = dst->popcount != NULL;
627
  unsigned char *popcountp = dst->popcount;
628
 
629
  for (i = 0; i < n; i++)
630
    {
631
      const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
632
      if (has_popcount)
633
        {
634
          bool wordchanged = (*dstp ^ tmp) != 0;
635
          if (wordchanged)
636
            *popcountp = do_popcount (tmp);
637
          popcountp++;
638
        }
639
      *dstp++ = tmp;
640
    }
641
#ifdef BITMAP_DEBUGGING
642
  if (has_popcount)
643
    sbitmap_verify_popcount (dst);
644
#endif
645
}
646
 
647
/* Return nonzero if A is a subset of B.  */
648
 
649
bool
650
sbitmap_a_subset_b_p (const_sbitmap a, const_sbitmap b)
651
{
652
  unsigned int i, n = a->size;
653
  const_sbitmap_ptr ap, bp;
654
 
655
  for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
656
    if ((*ap | *bp) != *bp)
657
      return false;
658
 
659
  return true;
660
}
661
 
662
/* Set DST to be (A or (B and C)).
663
   Return nonzero if any change is made.  */
664
 
665
bool
666
sbitmap_a_or_b_and_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
667
{
668
  unsigned int i, n = dst->size;
669
  sbitmap_ptr dstp = dst->elms;
670
  const_sbitmap_ptr ap = a->elms;
671
  const_sbitmap_ptr bp = b->elms;
672
  const_sbitmap_ptr cp = c->elms;
673
  SBITMAP_ELT_TYPE changed = 0;
674
 
675
  gcc_assert (!dst->popcount);
676
 
677
  for (i = 0; i < n; i++)
678
    {
679
      const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
680
      changed |= *dstp ^ tmp;
681
      *dstp++ = tmp;
682
    }
683
 
684
  return changed != 0;
685
}
686
 
687
void
688
sbitmap_a_or_b_and_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
689
{
690
  unsigned int i, n = dst->size;
691
  sbitmap_ptr dstp = dst->elms;
692
  const_sbitmap_ptr ap = a->elms;
693
  const_sbitmap_ptr bp = b->elms;
694
  const_sbitmap_ptr cp = c->elms;
695
 
696
  gcc_assert (!dst->popcount);
697
 
698
  for (i = 0; i < n; i++)
699
    *dstp++ = *ap++ | (*bp++ & *cp++);
700
}
701
 
702
/* Set DST to be (A and (B or C)).
703
   Return nonzero if any change is made.  */
704
 
705
bool
706
sbitmap_a_and_b_or_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
707
{
708
  unsigned int i, n = dst->size;
709
  sbitmap_ptr dstp = dst->elms;
710
  const_sbitmap_ptr ap = a->elms;
711
  const_sbitmap_ptr bp = b->elms;
712
  const_sbitmap_ptr cp = c->elms;
713
  SBITMAP_ELT_TYPE changed = 0;
714
 
715
  gcc_assert (!dst->popcount);
716
 
717
  for (i = 0; i < n; i++)
718
    {
719
      const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
720
      changed |= *dstp ^ tmp;
721
      *dstp++ = tmp;
722
    }
723
 
724
  return changed != 0;
725
}
726
 
727
void
728
sbitmap_a_and_b_or_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
729
{
730
  unsigned int i, n = dst->size;
731
  sbitmap_ptr dstp = dst->elms;
732
  const_sbitmap_ptr ap = a->elms;
733
  const_sbitmap_ptr bp = b->elms;
734
  const_sbitmap_ptr cp = c->elms;
735
 
736
  for (i = 0; i < n; i++)
737
    *dstp++ = *ap++ & (*bp++ | *cp++);
738
}
739
 
740
#ifdef IN_GCC
741
/* Set the bitmap DST to the intersection of SRC of successors of
742
   block number BB, using the new flow graph structures.  */
743
 
744
void
745
sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb)
746
{
747
  basic_block b = BASIC_BLOCK (bb);
748
  unsigned int set_size = dst->size;
749
  edge e;
750
  unsigned ix;
751
 
752
  gcc_assert (!dst->popcount);
753
 
754
  for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
755
    {
756
      e = EDGE_SUCC (b, ix);
757
      if (e->dest == EXIT_BLOCK_PTR)
758
        continue;
759
 
760
      sbitmap_copy (dst, src[e->dest->index]);
761
      break;
762
    }
763
 
764
  if (e == 0)
765
    sbitmap_ones (dst);
766
  else
767
    for (++ix; ix < EDGE_COUNT (b->succs); ix++)
768
      {
769
        unsigned int i;
770
        sbitmap_ptr p, r;
771
 
772
        e = EDGE_SUCC (b, ix);
773
        if (e->dest == EXIT_BLOCK_PTR)
774
          continue;
775
 
776
        p = src[e->dest->index]->elms;
777
        r = dst->elms;
778
        for (i = 0; i < set_size; i++)
779
          *r++ &= *p++;
780
      }
781
}
782
 
783
/* Set the bitmap DST to the intersection of SRC of predecessors of
784
   block number BB, using the new flow graph structures.  */
785
 
786
void
787
sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb)
788
{
789
  basic_block b = BASIC_BLOCK (bb);
790
  unsigned int set_size = dst->size;
791
  edge e;
792
  unsigned ix;
793
 
794
  gcc_assert (!dst->popcount);
795
 
796
  for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
797
    {
798
      e = EDGE_PRED (b, ix);
799
      if (e->src == ENTRY_BLOCK_PTR)
800
        continue;
801
 
802
      sbitmap_copy (dst, src[e->src->index]);
803
      break;
804
    }
805
 
806
  if (e == 0)
807
    sbitmap_ones (dst);
808
  else
809
    for (++ix; ix < EDGE_COUNT (b->preds); ix++)
810
      {
811
        unsigned int i;
812
        sbitmap_ptr p, r;
813
 
814
        e = EDGE_PRED (b, ix);
815
        if (e->src == ENTRY_BLOCK_PTR)
816
          continue;
817
 
818
        p = src[e->src->index]->elms;
819
        r = dst->elms;
820
        for (i = 0; i < set_size; i++)
821
          *r++ &= *p++;
822
      }
823
}
824
 
825
/* Set the bitmap DST to the union of SRC of successors of
826
   block number BB, using the new flow graph structures.  */
827
 
828
void
829
sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb)
830
{
831
  basic_block b = BASIC_BLOCK (bb);
832
  unsigned int set_size = dst->size;
833
  edge e;
834
  unsigned ix;
835
 
836
  gcc_assert (!dst->popcount);
837
 
838
  for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
839
    {
840
      e = EDGE_SUCC (b, ix);
841
      if (e->dest == EXIT_BLOCK_PTR)
842
        continue;
843
 
844
      sbitmap_copy (dst, src[e->dest->index]);
845
      break;
846
    }
847
 
848
  if (ix == EDGE_COUNT (b->succs))
849
    sbitmap_zero (dst);
850
  else
851
    for (ix++; ix < EDGE_COUNT (b->succs); ix++)
852
      {
853
        unsigned int i;
854
        sbitmap_ptr p, r;
855
 
856
        e = EDGE_SUCC (b, ix);
857
        if (e->dest == EXIT_BLOCK_PTR)
858
          continue;
859
 
860
        p = src[e->dest->index]->elms;
861
        r = dst->elms;
862
        for (i = 0; i < set_size; i++)
863
          *r++ |= *p++;
864
      }
865
}
866
 
867
/* Set the bitmap DST to the union of SRC of predecessors of
868
   block number BB, using the new flow graph structures.  */
869
 
870
void
871
sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb)
872
{
873
  basic_block b = BASIC_BLOCK (bb);
874
  unsigned int set_size = dst->size;
875
  edge e;
876
  unsigned ix;
877
 
878
  gcc_assert (!dst->popcount);
879
 
880
  for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
881
    {
882
      e = EDGE_PRED (b, ix);
883
      if (e->src== ENTRY_BLOCK_PTR)
884
        continue;
885
 
886
      sbitmap_copy (dst, src[e->src->index]);
887
      break;
888
    }
889
 
890
  if (ix == EDGE_COUNT (b->preds))
891
    sbitmap_zero (dst);
892
  else
893
    for (ix++; ix < EDGE_COUNT (b->preds); ix++)
894
      {
895
        unsigned int i;
896
        sbitmap_ptr p, r;
897
 
898
        e = EDGE_PRED (b, ix);
899
        if (e->src == ENTRY_BLOCK_PTR)
900
          continue;
901
 
902
        p = src[e->src->index]->elms;
903
        r = dst->elms;
904
        for (i = 0; i < set_size; i++)
905
          *r++ |= *p++;
906
      }
907
}
908
#endif
909
 
910
/* Return number of first bit set in the bitmap, -1 if none.  */
911
 
912
int
913
sbitmap_first_set_bit (const_sbitmap bmap)
914
{
915
  unsigned int n = 0;
916
  sbitmap_iterator sbi;
917
 
918
  EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi)
919
    return n;
920
  return -1;
921
}
922
 
923
/* Return number of last bit set in the bitmap, -1 if none.  */
924
 
925
int
926
sbitmap_last_set_bit (const_sbitmap bmap)
927
{
928
  int i;
929
  const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
930
 
931
  for (i = bmap->size - 1; i >= 0; i--)
932
    {
933
      const SBITMAP_ELT_TYPE word = ptr[i];
934
 
935
      if (word != 0)
936
        {
937
          unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
938
          SBITMAP_ELT_TYPE mask
939
            = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
940
 
941
          while (1)
942
            {
943
              if ((word & mask) != 0)
944
                return index;
945
 
946
              mask >>= 1;
947
              index--;
948
            }
949
        }
950
    }
951
 
952
  return -1;
953
}
954
 
955
void
956
dump_sbitmap (FILE *file, const_sbitmap bmap)
957
{
958
  unsigned int i, n, j;
959
  unsigned int set_size = bmap->size;
960
  unsigned int total_bits = bmap->n_bits;
961
 
962
  fprintf (file, "  ");
963
  for (i = n = 0; i < set_size && n < total_bits; i++)
964
    for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
965
      {
966
        if (n != 0 && n % 10 == 0)
967
          fprintf (file, " ");
968
 
969
        fprintf (file, "%d",
970
                 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
971
      }
972
 
973
  fprintf (file, "\n");
974
}
975
 
976
void
977
dump_sbitmap_file (FILE *file, const_sbitmap bmap)
978
{
979
  unsigned int i, pos;
980
 
981
  fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
982
 
983
  for (pos = 30, i = 0; i < bmap->n_bits; i++)
984
    if (TEST_BIT (bmap, i))
985
      {
986
        if (pos > 70)
987
          {
988
            fprintf (file, "\n  ");
989
            pos = 0;
990
          }
991
 
992
        fprintf (file, "%d ", i);
993
        pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
994
      }
995
 
996
  fprintf (file, "}\n");
997
}
998
 
999
void
1000
debug_sbitmap (const_sbitmap bmap)
1001
{
1002
  dump_sbitmap_file (stderr, bmap);
1003
}
1004
 
1005
void
1006
dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle,
1007
                     sbitmap *bmaps, int n_maps)
1008
{
1009
  int bb;
1010
 
1011
  fprintf (file, "%s\n", title);
1012
  for (bb = 0; bb < n_maps; bb++)
1013
    {
1014
      fprintf (file, "%s %d\n", subtitle, bb);
1015
      dump_sbitmap (file, bmaps[bb]);
1016
    }
1017
 
1018
  fprintf (file, "\n");
1019
}
1020
 
1021
#if GCC_VERSION < 3400
1022
/* Table of number of set bits in a character, indexed by value of char.  */
1023
static const unsigned char popcount_table[] =
1024
{
1025
    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,
1026
    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,
1027
    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,
1028
    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,
1029
    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,
1030
    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,
1031
    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,
1032
    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,
1033
};
1034
 
1035
/* Count the bits in an SBITMAP element A.  */
1036
 
1037
static unsigned long
1038
sbitmap_elt_popcount (SBITMAP_ELT_TYPE a)
1039
{
1040
  unsigned long ret = 0;
1041
  unsigned i;
1042
 
1043
  if (a == 0)
1044
    return 0;
1045
 
1046
  /* Just do this the table way for now  */
1047
  for (i = 0; i < SBITMAP_ELT_BITS; i += 8)
1048
    ret += popcount_table[(a >> i) & 0xff];
1049
  return ret;
1050
}
1051
#endif
1052
 
1053
/* Count the number of bits in SBITMAP a, up to bit MAXBIT.  */
1054
 
1055
unsigned long
1056
sbitmap_popcount (const_sbitmap a, unsigned long maxbit)
1057
{
1058
  unsigned long count = 0;
1059
  unsigned ix;
1060
  unsigned int lastword;
1061
 
1062
  if (maxbit == 0)
1063
    return 0;
1064
 
1065
  if (maxbit >= a->n_bits)
1066
    maxbit = a->n_bits;
1067
 
1068
  /* Count the bits in the full word.  */
1069
  lastword = MIN (a->size, SBITMAP_SET_SIZE (maxbit + 1) - 1);
1070
  for (ix = 0; ix < lastword; ix++)
1071
    {
1072
      if (a->popcount)
1073
        {
1074
          count += a->popcount[ix];
1075
#ifdef BITMAP_DEBUGGING
1076
          gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
1077
#endif
1078
        }
1079
      else
1080
        count += do_popcount (a->elms[ix]);
1081
    }
1082
 
1083
  /* Count the remaining bits.  */
1084
  if (lastword < a->size)
1085
    {
1086
      unsigned int bitindex;
1087
      SBITMAP_ELT_TYPE theword = a->elms[lastword];
1088
 
1089
      bitindex = maxbit % SBITMAP_ELT_BITS;
1090
      if (bitindex != 0)
1091
        {
1092
          theword &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - bitindex);
1093
          count += do_popcount (theword);
1094
        }
1095
    }
1096
  return count;
1097
}
1098
 

powered by: WebSVN 2.1.0

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