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

Subversion Repositories openrisc

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

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

Line No. Rev Author Line
1 38 julius
/* Simple bitmaps.
2
   Copyright (C) 1999, 2000, 2002, 2003, 2004, 2007
3
   Free Software Foundation, Inc.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "rtl.h"
26
#include "flags.h"
27
#include "hard-reg-set.h"
28
#include "obstack.h"
29
#include "basic-block.h"
30
 
31
/* Bitmap manipulation routines.  */
32
 
33
/* Allocate a simple bitmap of N_ELMS bits.  */
34
 
35
sbitmap
36
sbitmap_alloc (unsigned int n_elms)
37
{
38
  unsigned int bytes, size, amt;
39
  sbitmap bmap;
40
 
41
  size = SBITMAP_SET_SIZE (n_elms);
42
  bytes = size * sizeof (SBITMAP_ELT_TYPE);
43
  amt = (sizeof (struct simple_bitmap_def)
44
         + bytes - sizeof (SBITMAP_ELT_TYPE));
45
  bmap = xmalloc (amt);
46
  bmap->n_bits = n_elms;
47
  bmap->size = size;
48
  bmap->bytes = bytes;
49
  return bmap;
50
}
51
 
52
/* Resize a simple bitmap BMAP to N_ELMS bits.  If increasing the
53
   size of BMAP, clear the new bits to zero if the DEF argument
54
   is zero, and set them to one otherwise.  */
55
 
56
sbitmap
57
sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
58
{
59
  unsigned int bytes, size, amt;
60
  unsigned int last_bit;
61
 
62
  size = SBITMAP_SET_SIZE (n_elms);
63
  bytes = size * sizeof (SBITMAP_ELT_TYPE);
64
  if (bytes > bmap->bytes)
65
    {
66
      amt = (sizeof (struct simple_bitmap_def)
67
            + bytes - sizeof (SBITMAP_ELT_TYPE));
68
      bmap = xrealloc (bmap, amt);
69
    }
70
 
71
  if (n_elms > bmap->n_bits)
72
    {
73
      if (def)
74
        {
75
          memset (bmap->elms + bmap->size, -1, bytes - bmap->bytes);
76
 
77
          /* Set the new bits if the original last element.  */
78
          last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
79
          if (last_bit)
80
            bmap->elms[bmap->size - 1]
81
              |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
82
 
83
          /* Clear the unused bit in the new last element.  */
84
          last_bit = n_elms % SBITMAP_ELT_BITS;
85
          if (last_bit)
86
            bmap->elms[size - 1]
87
              &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
88
        }
89
      else
90
        memset (bmap->elms + bmap->size, 0, bytes - bmap->bytes);
91
    }
92
  else if (n_elms < bmap->n_bits)
93
    {
94
      /* Clear the surplus bits in the last word.  */
95
      last_bit = n_elms % SBITMAP_ELT_BITS;
96
      if (last_bit)
97
        bmap->elms[size - 1]
98
          &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
99
    }
100
 
101
  bmap->n_bits = n_elms;
102
  bmap->size = size;
103
  bmap->bytes = bytes;
104
  return bmap;
105
}
106
 
107
/* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized.  */
108
 
109
sbitmap
110
sbitmap_realloc (sbitmap src, unsigned int n_elms)
111
{
112
  unsigned int bytes, size, amt;
113
  sbitmap bmap;
114
 
115
  size = SBITMAP_SET_SIZE (n_elms);
116
  bytes = size * sizeof (SBITMAP_ELT_TYPE);
117
  amt = (sizeof (struct simple_bitmap_def)
118
         + bytes - sizeof (SBITMAP_ELT_TYPE));
119
 
120
  if (src->bytes  >= bytes)
121
    {
122
      src->n_bits = n_elms;
123
      return src;
124
    }
125
 
126
  bmap = (sbitmap) xrealloc (src, amt);
127
  bmap->n_bits = n_elms;
128
  bmap->size = size;
129
  bmap->bytes = bytes;
130
  return bmap;
131
}
132
 
133
/* Allocate a vector of N_VECS bitmaps of N_ELMS bits.  */
134
 
135
sbitmap *
136
sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
137
{
138
  unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
139
  sbitmap *bitmap_vector;
140
 
141
  size = SBITMAP_SET_SIZE (n_elms);
142
  bytes = size * sizeof (SBITMAP_ELT_TYPE);
143
  elm_bytes = (sizeof (struct simple_bitmap_def)
144
               + bytes - sizeof (SBITMAP_ELT_TYPE));
145
  vector_bytes = n_vecs * sizeof (sbitmap *);
146
 
147
  /* Round up `vector_bytes' to account for the alignment requirements
148
     of an sbitmap.  One could allocate the vector-table and set of sbitmaps
149
     separately, but that requires maintaining two pointers or creating
150
     a cover struct to hold both pointers (so our result is still just
151
     one pointer).  Neither is a bad idea, but this is simpler for now.  */
152
  {
153
    /* Based on DEFAULT_ALIGNMENT computation in obstack.c.  */
154
    struct { char x; SBITMAP_ELT_TYPE y; } align;
155
    int alignment = (char *) & align.y - & align.x;
156
    vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
157
  }
158
 
159
  amt = vector_bytes + (n_vecs * elm_bytes);
160
  bitmap_vector = xmalloc (amt);
161
 
162
  for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
163
    {
164
      sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
165
 
166
      bitmap_vector[i] = b;
167
      b->n_bits = n_elms;
168
      b->size = size;
169
      b->bytes = bytes;
170
    }
171
 
172
  return bitmap_vector;
173
}
174
 
175
/* Copy sbitmap SRC to DST.  */
176
 
177
void
178
sbitmap_copy (sbitmap dst, sbitmap src)
179
{
180
  memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
181
}
182
 
183
/* Determine if a == b.  */
184
int
185
sbitmap_equal (sbitmap a, sbitmap b)
186
{
187
  return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
188
}
189
 
190
/* Zero all elements in a bitmap.  */
191
 
192
void
193
sbitmap_zero (sbitmap bmap)
194
{
195
  memset (bmap->elms, 0, bmap->bytes);
196
}
197
 
198
/* Set all elements in a bitmap to ones.  */
199
 
200
void
201
sbitmap_ones (sbitmap bmap)
202
{
203
  unsigned int last_bit;
204
 
205
  memset (bmap->elms, -1, bmap->bytes);
206
 
207
  last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
208
  if (last_bit)
209
    bmap->elms[bmap->size - 1]
210
      = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
211
}
212
 
213
/* Zero a vector of N_VECS bitmaps.  */
214
 
215
void
216
sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs)
217
{
218
  unsigned int i;
219
 
220
  for (i = 0; i < n_vecs; i++)
221
    sbitmap_zero (bmap[i]);
222
}
223
 
224
/* Set a vector of N_VECS bitmaps to ones.  */
225
 
226
void
227
sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
228
{
229
  unsigned int i;
230
 
231
  for (i = 0; i < n_vecs; i++)
232
    sbitmap_ones (bmap[i]);
233
}
234
 
235
/* Set DST to be A union (B - C).
236
   DST = A | (B & ~C).
237
   Returns true if any change is made.  */
238
 
239
bool
240
sbitmap_union_of_diff_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
241
{
242
  unsigned int i, n = dst->size;
243
  sbitmap_ptr dstp = dst->elms;
244
  sbitmap_ptr ap = a->elms;
245
  sbitmap_ptr bp = b->elms;
246
  sbitmap_ptr cp = c->elms;
247
  SBITMAP_ELT_TYPE changed = 0;
248
 
249
  for (i = 0; i < n; i++)
250
    {
251
      SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
252
      changed |= *dstp ^ tmp;
253
      *dstp++ = tmp;
254
    }
255
 
256
  return changed != 0;
257
}
258
 
259
void
260
sbitmap_union_of_diff (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
261
{
262
  unsigned int i, n = dst->size;
263
  sbitmap_ptr dstp = dst->elms;
264
  sbitmap_ptr ap = a->elms;
265
  sbitmap_ptr bp = b->elms;
266
  sbitmap_ptr cp = c->elms;
267
 
268
  for (i = 0; i < n; i++)
269
    *dstp++ = *ap++ | (*bp++ & ~*cp++);
270
}
271
 
272
/* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
273
 
274
void
275
sbitmap_not (sbitmap dst, sbitmap src)
276
{
277
  unsigned int i, n = dst->size;
278
  sbitmap_ptr dstp = dst->elms;
279
  sbitmap_ptr srcp = src->elms;
280
  unsigned int last_bit;
281
 
282
  for (i = 0; i < n; i++)
283
    *dstp++ = ~*srcp++;
284
 
285
  /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones.  */
286
  last_bit = src->n_bits % SBITMAP_ELT_BITS;
287
  if (last_bit)
288
    dst->elms[n-1] = dst->elms[n-1]
289
      & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
290
}
291
 
292
/* Set the bits in DST to be the difference between the bits
293
   in A and the bits in B. i.e. dst = a & (~b).  */
294
 
295
void
296
sbitmap_difference (sbitmap dst, sbitmap a, sbitmap b)
297
{
298
  unsigned int i, dst_size = dst->size;
299
  unsigned int min_size = dst->size;
300
  sbitmap_ptr dstp = dst->elms;
301
  sbitmap_ptr ap = a->elms;
302
  sbitmap_ptr bp = b->elms;
303
 
304
  /* A should be at least as large as DEST, to have a defined source.  */
305
  gcc_assert (a->size >= dst_size);
306
  /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
307
     only copy the subtrahend into dest.  */
308
  if (b->size < min_size)
309
    min_size = b->size;
310
  for (i = 0; i < min_size; i++)
311
    *dstp++ = *ap++ & (~*bp++);
312
  /* Now fill the rest of dest from A, if B was too short.
313
     This makes sense only when destination and A differ.  */
314
  if (dst != a && i != dst_size)
315
    for (; i < dst_size; i++)
316
      *dstp++ = *ap++;
317
}
318
 
319
/* Return true if there are any bits set in A are also set in B.
320
   Return false otherwise.  */
321
 
322
bool
323
sbitmap_any_common_bits (sbitmap a, sbitmap b)
324
{
325
  sbitmap_ptr ap = a->elms;
326
  sbitmap_ptr bp = b->elms;
327
  unsigned int i, n;
328
 
329
  n = MIN (a->size, b->size);
330
  for (i = 0; i < n; i++)
331
    if ((*ap++ & *bp++) != 0)
332
      return true;
333
 
334
  return false;
335
}
336
 
337
/* Set DST to be (A and B).
338
   Return nonzero if any change is made.  */
339
 
340
bool
341
sbitmap_a_and_b_cg (sbitmap dst, sbitmap a, sbitmap b)
342
{
343
  unsigned int i, n = dst->size;
344
  sbitmap_ptr dstp = dst->elms;
345
  sbitmap_ptr ap = a->elms;
346
  sbitmap_ptr bp = b->elms;
347
  SBITMAP_ELT_TYPE changed = 0;
348
 
349
  for (i = 0; i < n; i++)
350
    {
351
      SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
352
      changed |= *dstp ^ tmp;
353
      *dstp++ = tmp;
354
    }
355
 
356
  return changed != 0;
357
}
358
 
359
void
360
sbitmap_a_and_b (sbitmap dst, sbitmap a, sbitmap b)
361
{
362
  unsigned int i, n = dst->size;
363
  sbitmap_ptr dstp = dst->elms;
364
  sbitmap_ptr ap = a->elms;
365
  sbitmap_ptr bp = b->elms;
366
 
367
  for (i = 0; i < n; i++)
368
    *dstp++ = *ap++ & *bp++;
369
}
370
 
371
/* Set DST to be (A xor B)).
372
   Return nonzero if any change is made.  */
373
 
374
bool
375
sbitmap_a_xor_b_cg (sbitmap dst, sbitmap a, sbitmap b)
376
{
377
  unsigned int i, n = dst->size;
378
  sbitmap_ptr dstp = dst->elms;
379
  sbitmap_ptr ap = a->elms;
380
  sbitmap_ptr bp = b->elms;
381
  SBITMAP_ELT_TYPE changed = 0;
382
 
383
  for (i = 0; i < n; i++)
384
    {
385
      SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
386
      changed |= *dstp ^ tmp;
387
      *dstp++ = tmp;
388
    }
389
 
390
  return changed != 0;
391
}
392
 
393
void
394
sbitmap_a_xor_b (sbitmap dst, sbitmap a, sbitmap b)
395
{
396
  unsigned int i, n = dst->size;
397
  sbitmap_ptr dstp = dst->elms;
398
  sbitmap_ptr ap = a->elms;
399
  sbitmap_ptr bp = b->elms;
400
 
401
  for (i = 0; i < n; i++)
402
    *dstp++ = *ap++ ^ *bp++;
403
}
404
 
405
/* Set DST to be (A or B)).
406
   Return nonzero if any change is made.  */
407
 
408
bool
409
sbitmap_a_or_b_cg (sbitmap dst, sbitmap a, sbitmap b)
410
{
411
  unsigned int i, n = dst->size;
412
  sbitmap_ptr dstp = dst->elms;
413
  sbitmap_ptr ap = a->elms;
414
  sbitmap_ptr bp = b->elms;
415
  SBITMAP_ELT_TYPE changed = 0;
416
 
417
  for (i = 0; i < n; i++)
418
    {
419
      SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
420
      changed |= *dstp ^ tmp;
421
      *dstp++ = tmp;
422
    }
423
 
424
  return changed != 0;
425
}
426
 
427
void
428
sbitmap_a_or_b (sbitmap dst, sbitmap a, sbitmap b)
429
{
430
  unsigned int i, n = dst->size;
431
  sbitmap_ptr dstp = dst->elms;
432
  sbitmap_ptr ap = a->elms;
433
  sbitmap_ptr bp = b->elms;
434
 
435
  for (i = 0; i < n; i++)
436
    *dstp++ = *ap++ | *bp++;
437
}
438
 
439
/* Return nonzero if A is a subset of B.  */
440
 
441
bool
442
sbitmap_a_subset_b_p (sbitmap a, sbitmap b)
443
{
444
  unsigned int i, n = a->size;
445
  sbitmap_ptr ap, bp;
446
 
447
  for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
448
    if ((*ap | *bp) != *bp)
449
      return false;
450
 
451
  return true;
452
}
453
 
454
/* Set DST to be (A or (B and C)).
455
   Return nonzero if any change is made.  */
456
 
457
bool
458
sbitmap_a_or_b_and_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
459
{
460
  unsigned int i, n = dst->size;
461
  sbitmap_ptr dstp = dst->elms;
462
  sbitmap_ptr ap = a->elms;
463
  sbitmap_ptr bp = b->elms;
464
  sbitmap_ptr cp = c->elms;
465
  SBITMAP_ELT_TYPE changed = 0;
466
 
467
  for (i = 0; i < n; i++)
468
    {
469
      SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
470
      changed |= *dstp ^ tmp;
471
      *dstp++ = tmp;
472
    }
473
 
474
  return changed != 0;
475
}
476
 
477
void
478
sbitmap_a_or_b_and_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
479
{
480
  unsigned int i, n = dst->size;
481
  sbitmap_ptr dstp = dst->elms;
482
  sbitmap_ptr ap = a->elms;
483
  sbitmap_ptr bp = b->elms;
484
  sbitmap_ptr cp = c->elms;
485
 
486
  for (i = 0; i < n; i++)
487
    *dstp++ = *ap++ | (*bp++ & *cp++);
488
}
489
 
490
/* Set DST to be (A and (B or C)).
491
   Return nonzero if any change is made.  */
492
 
493
bool
494
sbitmap_a_and_b_or_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
495
{
496
  unsigned int i, n = dst->size;
497
  sbitmap_ptr dstp = dst->elms;
498
  sbitmap_ptr ap = a->elms;
499
  sbitmap_ptr bp = b->elms;
500
  sbitmap_ptr cp = c->elms;
501
  SBITMAP_ELT_TYPE changed = 0;
502
 
503
  for (i = 0; i < n; i++)
504
    {
505
      SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
506
      changed |= *dstp ^ tmp;
507
      *dstp++ = tmp;
508
    }
509
 
510
  return changed != 0;
511
}
512
 
513
void
514
sbitmap_a_and_b_or_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
515
{
516
  unsigned int i, n = dst->size;
517
  sbitmap_ptr dstp = dst->elms;
518
  sbitmap_ptr ap = a->elms;
519
  sbitmap_ptr bp = b->elms;
520
  sbitmap_ptr cp = c->elms;
521
 
522
  for (i = 0; i < n; i++)
523
    *dstp++ = *ap++ & (*bp++ | *cp++);
524
}
525
 
526
#ifdef IN_GCC
527
/* Set the bitmap DST to the intersection of SRC of successors of
528
   block number BB, using the new flow graph structures.  */
529
 
530
void
531
sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb)
532
{
533
  basic_block b = BASIC_BLOCK (bb);
534
  unsigned int set_size = dst->size;
535
  edge e;
536
  unsigned ix;
537
 
538
  for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
539
    {
540
      e = EDGE_SUCC (b, ix);
541
      if (e->dest == EXIT_BLOCK_PTR)
542
        continue;
543
 
544
      sbitmap_copy (dst, src[e->dest->index]);
545
      break;
546
    }
547
 
548
  if (e == 0)
549
    sbitmap_ones (dst);
550
  else
551
    for (++ix; ix < EDGE_COUNT (b->succs); ix++)
552
      {
553
        unsigned int i;
554
        sbitmap_ptr p, r;
555
 
556
        e = EDGE_SUCC (b, ix);
557
        if (e->dest == EXIT_BLOCK_PTR)
558
          continue;
559
 
560
        p = src[e->dest->index]->elms;
561
        r = dst->elms;
562
        for (i = 0; i < set_size; i++)
563
          *r++ &= *p++;
564
      }
565
}
566
 
567
/* Set the bitmap DST to the intersection of SRC of predecessors of
568
   block number BB, using the new flow graph structures.  */
569
 
570
void
571
sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb)
572
{
573
  basic_block b = BASIC_BLOCK (bb);
574
  unsigned int set_size = dst->size;
575
  edge e;
576
  unsigned ix;
577
 
578
  for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
579
    {
580
      e = EDGE_PRED (b, ix);
581
      if (e->src == ENTRY_BLOCK_PTR)
582
        continue;
583
 
584
      sbitmap_copy (dst, src[e->src->index]);
585
      break;
586
    }
587
 
588
  if (e == 0)
589
    sbitmap_ones (dst);
590
  else
591
    for (++ix; ix < EDGE_COUNT (b->preds); ix++)
592
      {
593
        unsigned int i;
594
        sbitmap_ptr p, r;
595
 
596
        e = EDGE_PRED (b, ix);
597
        if (e->src == ENTRY_BLOCK_PTR)
598
          continue;
599
 
600
        p = src[e->src->index]->elms;
601
        r = dst->elms;
602
        for (i = 0; i < set_size; i++)
603
          *r++ &= *p++;
604
      }
605
}
606
 
607
/* Set the bitmap DST to the union of SRC of successors of
608
   block number BB, using the new flow graph structures.  */
609
 
610
void
611
sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb)
612
{
613
  basic_block b = BASIC_BLOCK (bb);
614
  unsigned int set_size = dst->size;
615
  edge e;
616
  unsigned ix;
617
 
618
  for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
619
    {
620
      e = EDGE_SUCC (b, ix);
621
      if (e->dest == EXIT_BLOCK_PTR)
622
        continue;
623
 
624
      sbitmap_copy (dst, src[e->dest->index]);
625
      break;
626
    }
627
 
628
  if (ix == EDGE_COUNT (b->succs))
629
    sbitmap_zero (dst);
630
  else
631
    for (ix++; ix < EDGE_COUNT (b->succs); ix++)
632
      {
633
        unsigned int i;
634
        sbitmap_ptr p, r;
635
 
636
        e = EDGE_SUCC (b, ix);
637
        if (e->dest == EXIT_BLOCK_PTR)
638
          continue;
639
 
640
        p = src[e->dest->index]->elms;
641
        r = dst->elms;
642
        for (i = 0; i < set_size; i++)
643
          *r++ |= *p++;
644
      }
645
}
646
 
647
/* Set the bitmap DST to the union of SRC of predecessors of
648
   block number BB, using the new flow graph structures.  */
649
 
650
void
651
sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb)
652
{
653
  basic_block b = BASIC_BLOCK (bb);
654
  unsigned int set_size = dst->size;
655
  edge e;
656
  unsigned ix;
657
 
658
  for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
659
    {
660
      e = EDGE_PRED (b, ix);
661
      if (e->src== ENTRY_BLOCK_PTR)
662
        continue;
663
 
664
      sbitmap_copy (dst, src[e->src->index]);
665
      break;
666
    }
667
 
668
  if (ix == EDGE_COUNT (b->preds))
669
    sbitmap_zero (dst);
670
  else
671
    for (ix++; ix < EDGE_COUNT (b->preds); ix++)
672
      {
673
        unsigned int i;
674
        sbitmap_ptr p, r;
675
 
676
        e = EDGE_PRED (b, ix);
677
        if (e->src == ENTRY_BLOCK_PTR)
678
          continue;
679
 
680
        p = src[e->src->index]->elms;
681
        r = dst->elms;
682
        for (i = 0; i < set_size; i++)
683
          *r++ |= *p++;
684
      }
685
}
686
#endif
687
 
688
/* Return number of first bit set in the bitmap, -1 if none.  */
689
 
690
int
691
sbitmap_first_set_bit (sbitmap bmap)
692
{
693
  unsigned int n = 0;
694
  sbitmap_iterator sbi;
695
 
696
  EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi)
697
    return n;
698
  return -1;
699
}
700
 
701
/* Return number of last bit set in the bitmap, -1 if none.  */
702
 
703
int
704
sbitmap_last_set_bit (sbitmap bmap)
705
{
706
  int i;
707
  SBITMAP_ELT_TYPE *ptr = bmap->elms;
708
 
709
  for (i = bmap->size - 1; i >= 0; i--)
710
    {
711
      SBITMAP_ELT_TYPE word = ptr[i];
712
 
713
      if (word != 0)
714
        {
715
          unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
716
          SBITMAP_ELT_TYPE mask
717
            = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
718
 
719
          while (1)
720
            {
721
              if ((word & mask) != 0)
722
                return index;
723
 
724
              mask >>= 1;
725
              index--;
726
            }
727
        }
728
    }
729
 
730
  return -1;
731
}
732
 
733
void
734
dump_sbitmap (FILE *file, sbitmap bmap)
735
{
736
  unsigned int i, n, j;
737
  unsigned int set_size = bmap->size;
738
  unsigned int total_bits = bmap->n_bits;
739
 
740
  fprintf (file, "  ");
741
  for (i = n = 0; i < set_size && n < total_bits; i++)
742
    for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
743
      {
744
        if (n != 0 && n % 10 == 0)
745
          fprintf (file, " ");
746
 
747
        fprintf (file, "%d",
748
                 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
749
      }
750
 
751
  fprintf (file, "\n");
752
}
753
 
754
void
755
dump_sbitmap_file (FILE *file, sbitmap bmap)
756
{
757
  unsigned int i, pos;
758
 
759
  fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
760
 
761
  for (pos = 30, i = 0; i < bmap->n_bits; i++)
762
    if (TEST_BIT (bmap, i))
763
      {
764
        if (pos > 70)
765
          {
766
            fprintf (file, "\n  ");
767
            pos = 0;
768
          }
769
 
770
        fprintf (file, "%d ", i);
771
        pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
772
      }
773
 
774
  fprintf (file, "}\n");
775
}
776
 
777
void
778
debug_sbitmap (sbitmap bmap)
779
{
780
  dump_sbitmap_file (stderr, bmap);
781
}
782
 
783
void
784
dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle,
785
                     sbitmap *bmaps, int n_maps)
786
{
787
  int bb;
788
 
789
  fprintf (file, "%s\n", title);
790
  for (bb = 0; bb < n_maps; bb++)
791
    {
792
      fprintf (file, "%s %d\n", subtitle, bb);
793
      dump_sbitmap (file, bmaps[bb]);
794
    }
795
 
796
  fprintf (file, "\n");
797
}

powered by: WebSVN 2.1.0

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