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


/* Simple bitmaps.
   Copyright (C) 1999, 2000, 2002, 2003, 2004, 2007
   Free Software Foundation, Inc.
 
This file is part of GCC.
 
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
 
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.
 
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */
 
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "flags.h"
#include "hard-reg-set.h"
#include "obstack.h"
#include "basic-block.h"
 
/* Bitmap manipulation routines.  */
 
/* Allocate a simple bitmap of N_ELMS bits.  */
 
sbitmap
sbitmap_alloc (unsigned int n_elms)
{
  unsigned int bytes, size, amt;
  sbitmap bmap;
 
  size = SBITMAP_SET_SIZE (n_elms);
  bytes = size * sizeof (SBITMAP_ELT_TYPE);
  amt = (sizeof (struct simple_bitmap_def)
         + bytes - sizeof (SBITMAP_ELT_TYPE));
  bmap = xmalloc (amt);
  bmap->n_bits = n_elms;
  bmap->size = size;
  bmap->bytes = bytes;
  return bmap;
}
 
/* Resize a simple bitmap BMAP to N_ELMS bits.  If increasing the
   size of BMAP, clear the new bits to zero if the DEF argument
   is zero, and set them to one otherwise.  */
 
sbitmap
sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
{
  unsigned int bytes, size, amt;
  unsigned int last_bit;
 
  size = SBITMAP_SET_SIZE (n_elms);
  bytes = size * sizeof (SBITMAP_ELT_TYPE);
  if (bytes > bmap->bytes)
    {
      amt = (sizeof (struct simple_bitmap_def)
            + bytes - sizeof (SBITMAP_ELT_TYPE));
      bmap = xrealloc (bmap, amt);
    }
 
  if (n_elms > bmap->n_bits)
    {
      if (def)
        {
          memset (bmap->elms + bmap->size, -1, bytes - bmap->bytes);
 
          /* Set the new bits if the original last element.  */
          last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
          if (last_bit)
            bmap->elms[bmap->size - 1]
              |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
 
          /* Clear the unused bit in the new last element.  */
          last_bit = n_elms % SBITMAP_ELT_BITS;
          if (last_bit)
            bmap->elms[size - 1]
              &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
        }
      else
        memset (bmap->elms + bmap->size, 0, bytes - bmap->bytes);
    }
  else if (n_elms < bmap->n_bits)
    {
      /* Clear the surplus bits in the last word.  */
      last_bit = n_elms % SBITMAP_ELT_BITS;
      if (last_bit)
        bmap->elms[size - 1]
          &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
    }
 
  bmap->n_bits = n_elms;
  bmap->size = size;
  bmap->bytes = bytes;
  return bmap;
}
 
/* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized.  */
 
sbitmap
sbitmap_realloc (sbitmap src, unsigned int n_elms)
{
  unsigned int bytes, size, amt;
  sbitmap bmap;
 
  size = SBITMAP_SET_SIZE (n_elms);
  bytes = size * sizeof (SBITMAP_ELT_TYPE);
  amt = (sizeof (struct simple_bitmap_def)
         + bytes - sizeof (SBITMAP_ELT_TYPE));
 
  if (src->bytes  >= bytes)
    {
      src->n_bits = n_elms;
      return src;
    }
 
  bmap = (sbitmap) xrealloc (src, amt);
  bmap->n_bits = n_elms;
  bmap->size = size;
  bmap->bytes = bytes;
  return bmap;
}
 
/* Allocate a vector of N_VECS bitmaps of N_ELMS bits.  */
 
sbitmap *
sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
{
  unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
  sbitmap *bitmap_vector;
 
  size = SBITMAP_SET_SIZE (n_elms);
  bytes = size * sizeof (SBITMAP_ELT_TYPE);
  elm_bytes = (sizeof (struct simple_bitmap_def)
               + bytes - sizeof (SBITMAP_ELT_TYPE));
  vector_bytes = n_vecs * sizeof (sbitmap *);
 
  /* Round up `vector_bytes' to account for the alignment requirements
     of an sbitmap.  One could allocate the vector-table and set of sbitmaps
     separately, but that requires maintaining two pointers or creating
     a cover struct to hold both pointers (so our result is still just
     one pointer).  Neither is a bad idea, but this is simpler for now.  */
  {
    /* Based on DEFAULT_ALIGNMENT computation in obstack.c.  */
    struct { char x; SBITMAP_ELT_TYPE y; } align;
    int alignment = (char *) & align.y - & align.x;
    vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
  }
 
  amt = vector_bytes + (n_vecs * elm_bytes);
  bitmap_vector = xmalloc (amt);
 
  for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
    {
      sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
 
      bitmap_vector[i] = b;
      b->n_bits = n_elms;
      b->size = size;
      b->bytes = bytes;
    }
 
  return bitmap_vector;
}
 
/* Copy sbitmap SRC to DST.  */
 
void
sbitmap_copy (sbitmap dst, sbitmap src)
{
  memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
}
 
/* Determine if a == b.  */
int
sbitmap_equal (sbitmap a, sbitmap b)
{
  return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
}
 
/* Zero all elements in a bitmap.  */
 
void
sbitmap_zero (sbitmap bmap)
{
  memset (bmap->elms, 0, bmap->bytes);
}
 
/* Set all elements in a bitmap to ones.  */
 
void
sbitmap_ones (sbitmap bmap)
{
  unsigned int last_bit;
 
  memset (bmap->elms, -1, bmap->bytes);
 
  last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
  if (last_bit)
    bmap->elms[bmap->size - 1]
      = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
}
 
/* Zero a vector of N_VECS bitmaps.  */
 
void
sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs)
{
  unsigned int i;
 
  for (i = 0; i < n_vecs; i++)
    sbitmap_zero (bmap[i]);
}
 
/* Set a vector of N_VECS bitmaps to ones.  */
 
void
sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
{
  unsigned int i;
 
  for (i = 0; i < n_vecs; i++)
    sbitmap_ones (bmap[i]);
}
 
/* Set DST to be A union (B - C).
   DST = A | (B & ~C).
   Returns true if any change is made.  */
 
bool
sbitmap_union_of_diff_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
  sbitmap_ptr cp = c->elms;
  SBITMAP_ELT_TYPE changed = 0;
 
  for (i = 0; i < n; i++)
    {
      SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
      changed |= *dstp ^ tmp;
      *dstp++ = tmp;
    }
 
  return changed != 0;
}
 
void
sbitmap_union_of_diff (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
  sbitmap_ptr cp = c->elms;
 
  for (i = 0; i < n; i++)
    *dstp++ = *ap++ | (*bp++ & ~*cp++);
}
 
/* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
 
void
sbitmap_not (sbitmap dst, sbitmap src)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr srcp = src->elms;
  unsigned int last_bit;
 
  for (i = 0; i < n; i++)
    *dstp++ = ~*srcp++;
 
  /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones.  */
  last_bit = src->n_bits % SBITMAP_ELT_BITS;
  if (last_bit)
    dst->elms[n-1] = dst->elms[n-1]
      & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
}
 
/* Set the bits in DST to be the difference between the bits
   in A and the bits in B. i.e. dst = a & (~b).  */
 
void
sbitmap_difference (sbitmap dst, sbitmap a, sbitmap b)
{
  unsigned int i, dst_size = dst->size;
  unsigned int min_size = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
 
  /* A should be at least as large as DEST, to have a defined source.  */
  gcc_assert (a->size >= dst_size);
  /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
     only copy the subtrahend into dest.  */
  if (b->size < min_size)
    min_size = b->size;
  for (i = 0; i < min_size; i++)
    *dstp++ = *ap++ & (~*bp++);
  /* Now fill the rest of dest from A, if B was too short.
     This makes sense only when destination and A differ.  */
  if (dst != a && i != dst_size)
    for (; i < dst_size; i++)
      *dstp++ = *ap++;
}
 
/* Return true if there are any bits set in A are also set in B.
   Return false otherwise.  */
 
bool
sbitmap_any_common_bits (sbitmap a, sbitmap b)
{
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
  unsigned int i, n;
 
  n = MIN (a->size, b->size);
  for (i = 0; i < n; i++)
    if ((*ap++ & *bp++) != 0)
      return true;
 
  return false;
}
 
/* Set DST to be (A and B).
   Return nonzero if any change is made.  */
 
bool
sbitmap_a_and_b_cg (sbitmap dst, sbitmap a, sbitmap b)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
  SBITMAP_ELT_TYPE changed = 0;
 
  for (i = 0; i < n; i++)
    {
      SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
      changed |= *dstp ^ tmp;
      *dstp++ = tmp;
    }
 
  return changed != 0;
}
 
void
sbitmap_a_and_b (sbitmap dst, sbitmap a, sbitmap b)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
 
  for (i = 0; i < n; i++)
    *dstp++ = *ap++ & *bp++;
}
 
/* Set DST to be (A xor B)).
   Return nonzero if any change is made.  */
 
bool
sbitmap_a_xor_b_cg (sbitmap dst, sbitmap a, sbitmap b)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
  SBITMAP_ELT_TYPE changed = 0;
 
  for (i = 0; i < n; i++)
    {
      SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
      changed |= *dstp ^ tmp;
      *dstp++ = tmp;
    }
 
  return changed != 0;
}
 
void
sbitmap_a_xor_b (sbitmap dst, sbitmap a, sbitmap b)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
 
  for (i = 0; i < n; i++)
    *dstp++ = *ap++ ^ *bp++;
}
 
/* Set DST to be (A or B)).
   Return nonzero if any change is made.  */
 
bool
sbitmap_a_or_b_cg (sbitmap dst, sbitmap a, sbitmap b)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
  SBITMAP_ELT_TYPE changed = 0;
 
  for (i = 0; i < n; i++)
    {
      SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
      changed |= *dstp ^ tmp;
      *dstp++ = tmp;
    }
 
  return changed != 0;
}
 
void
sbitmap_a_or_b (sbitmap dst, sbitmap a, sbitmap b)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
 
  for (i = 0; i < n; i++)
    *dstp++ = *ap++ | *bp++;
}
 
/* Return nonzero if A is a subset of B.  */
 
bool
sbitmap_a_subset_b_p (sbitmap a, sbitmap b)
{
  unsigned int i, n = a->size;
  sbitmap_ptr ap, bp;
 
  for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
    if ((*ap | *bp) != *bp)
      return false;
 
  return true;
}
 
/* Set DST to be (A or (B and C)).
   Return nonzero if any change is made.  */
 
bool
sbitmap_a_or_b_and_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
  sbitmap_ptr cp = c->elms;
  SBITMAP_ELT_TYPE changed = 0;
 
  for (i = 0; i < n; i++)
    {
      SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
      changed |= *dstp ^ tmp;
      *dstp++ = tmp;
    }
 
  return changed != 0;
}
 
void
sbitmap_a_or_b_and_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
  sbitmap_ptr cp = c->elms;
 
  for (i = 0; i < n; i++)
    *dstp++ = *ap++ | (*bp++ & *cp++);
}
 
/* Set DST to be (A and (B or C)).
   Return nonzero if any change is made.  */
 
bool
sbitmap_a_and_b_or_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
  sbitmap_ptr cp = c->elms;
  SBITMAP_ELT_TYPE changed = 0;
 
  for (i = 0; i < n; i++)
    {
      SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
      changed |= *dstp ^ tmp;
      *dstp++ = tmp;
    }
 
  return changed != 0;
}
 
void
sbitmap_a_and_b_or_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
{
  unsigned int i, n = dst->size;
  sbitmap_ptr dstp = dst->elms;
  sbitmap_ptr ap = a->elms;
  sbitmap_ptr bp = b->elms;
  sbitmap_ptr cp = c->elms;
 
  for (i = 0; i < n; i++)
    *dstp++ = *ap++ & (*bp++ | *cp++);
}
 
#ifdef IN_GCC
/* Set the bitmap DST to the intersection of SRC of successors of
   block number BB, using the new flow graph structures.  */
 
void
sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb)
{
  basic_block b = BASIC_BLOCK (bb);
  unsigned int set_size = dst->size;
  edge e;
  unsigned ix;
 
  for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
    {
      e = EDGE_SUCC (b, ix);
      if (e->dest == EXIT_BLOCK_PTR)
        continue;
 
      sbitmap_copy (dst, src[e->dest->index]);
      break;
    }
 
  if (e == 0)
    sbitmap_ones (dst);
  else
    for (++ix; ix < EDGE_COUNT (b->succs); ix++)
      {
        unsigned int i;
        sbitmap_ptr p, r;
 
        e = EDGE_SUCC (b, ix);
        if (e->dest == EXIT_BLOCK_PTR)
          continue;
 
        p = src[e->dest->index]->elms;
        r = dst->elms;
        for (i = 0; i < set_size; i++)
          *r++ &= *p++;
      }
}
 
/* Set the bitmap DST to the intersection of SRC of predecessors of
   block number BB, using the new flow graph structures.  */
 
void
sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb)
{
  basic_block b = BASIC_BLOCK (bb);
  unsigned int set_size = dst->size;
  edge e;
  unsigned ix;
 
  for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
    {
      e = EDGE_PRED (b, ix);
      if (e->src == ENTRY_BLOCK_PTR)
        continue;
 
      sbitmap_copy (dst, src[e->src->index]);
      break;
    }
 
  if (e == 0)
    sbitmap_ones (dst);
  else
    for (++ix; ix < EDGE_COUNT (b->preds); ix++)
      {
        unsigned int i;
        sbitmap_ptr p, r;
 
        e = EDGE_PRED (b, ix);
        if (e->src == ENTRY_BLOCK_PTR)
          continue;
 
        p = src[e->src->index]->elms;
        r = dst->elms;
        for (i = 0; i < set_size; i++)
          *r++ &= *p++;
      }
}
 
/* Set the bitmap DST to the union of SRC of successors of
   block number BB, using the new flow graph structures.  */
 
void
sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb)
{
  basic_block b = BASIC_BLOCK (bb);
  unsigned int set_size = dst->size;
  edge e;
  unsigned ix;
 
  for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
    {
      e = EDGE_SUCC (b, ix);
      if (e->dest == EXIT_BLOCK_PTR)
        continue;
 
      sbitmap_copy (dst, src[e->dest->index]);
      break;
    }
 
  if (ix == EDGE_COUNT (b->succs))
    sbitmap_zero (dst);
  else
    for (ix++; ix < EDGE_COUNT (b->succs); ix++)
      {
        unsigned int i;
        sbitmap_ptr p, r;
 
        e = EDGE_SUCC (b, ix);
        if (e->dest == EXIT_BLOCK_PTR)
          continue;
 
        p = src[e->dest->index]->elms;
        r = dst->elms;
        for (i = 0; i < set_size; i++)
          *r++ |= *p++;
      }
}
 
/* Set the bitmap DST to the union of SRC of predecessors of
   block number BB, using the new flow graph structures.  */
 
void
sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb)
{
  basic_block b = BASIC_BLOCK (bb);
  unsigned int set_size = dst->size;
  edge e;
  unsigned ix;
 
  for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
    {
      e = EDGE_PRED (b, ix);
      if (e->src== ENTRY_BLOCK_PTR)
        continue;
 
      sbitmap_copy (dst, src[e->src->index]);
      break;
    }
 
  if (ix == EDGE_COUNT (b->preds))
    sbitmap_zero (dst);
  else
    for (ix++; ix < EDGE_COUNT (b->preds); ix++)
      {
        unsigned int i;
        sbitmap_ptr p, r;
 
        e = EDGE_PRED (b, ix);
        if (e->src == ENTRY_BLOCK_PTR)
          continue;
 
        p = src[e->src->index]->elms;
        r = dst->elms;
        for (i = 0; i < set_size; i++)
          *r++ |= *p++;
      }
}
#endif
 
/* Return number of first bit set in the bitmap, -1 if none.  */
 
int
sbitmap_first_set_bit (sbitmap bmap)
{
  unsigned int n = 0;
  sbitmap_iterator sbi;
 
  EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi)
    return n;
  return -1;
}
 
/* Return number of last bit set in the bitmap, -1 if none.  */
 
int
sbitmap_last_set_bit (sbitmap bmap)
{
  int i;
  SBITMAP_ELT_TYPE *ptr = bmap->elms;
 
  for (i = bmap->size - 1; i >= 0; i--)
    {
      SBITMAP_ELT_TYPE word = ptr[i];
 
      if (word != 0)
        {
          unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
          SBITMAP_ELT_TYPE mask
            = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
 
          while (1)
            {
              if ((word & mask) != 0)
                return index;
 
              mask >>= 1;
              index--;
            }
        }
    }
 
  return -1;
}
 
void
dump_sbitmap (FILE *file, sbitmap bmap)
{
  unsigned int i, n, j;
  unsigned int set_size = bmap->size;
  unsigned int total_bits = bmap->n_bits;
 
  fprintf (file, "  ");
  for (i = n = 0; i < set_size && n < total_bits; i++)
    for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
      {
        if (n != 0 && n % 10 == 0)
          fprintf (file, " ");
 
        fprintf (file, "%d",
                 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
      }
 
  fprintf (file, "\n");
}
 
void
dump_sbitmap_file (FILE *file, sbitmap bmap)
{
  unsigned int i, pos;
 
  fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
 
  for (pos = 30, i = 0; i < bmap->n_bits; i++)
    if (TEST_BIT (bmap, i))
      {
        if (pos > 70)
          {
            fprintf (file, "\n  ");
            pos = 0;
          }
 
        fprintf (file, "%d ", i);
        pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
      }
 
  fprintf (file, "}\n");
}
 
void
debug_sbitmap (sbitmap bmap)
{
  dump_sbitmap_file (stderr, bmap);
}
 
void
dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle,
                     sbitmap *bmaps, int n_maps)
{
  int bb;
 
  fprintf (file, "%s\n", title);
  for (bb = 0; bb < n_maps; bb++)
    {
      fprintf (file, "%s %d\n", subtitle, bb);
      dump_sbitmap (file, bmaps[bb]);
    }
 
  fprintf (file, "\n");
}

Browse

Tools

Subversion Repositories openrisc

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

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			`}`