* ipa-inline.c (cgraph_early_inlining): Handle flattening too.

[pf3gnuchains/gcc-fork.git] / gcc / sbitmap.c

diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c
index acc40a1..205b182 100644 (file)
--- a/gcc/sbitmap.c
+++ b/gcc/sbitmap.c
@@ -1,12 +1,12 @@
 /* Simple bitmaps.
-   Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007
+   Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007, 2008
    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 2, or (at your option) any later
+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
@@ -15,9 +15,8 @@ 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 COPYING.  If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA.  */
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
 
 #include "config.h"
 #include "system.h"
@@ -28,6 +27,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "hard-reg-set.h"
 #include "obstack.h"
 #include "basic-block.h"
+#include "sbitmap.h"
 
 #if GCC_VERSION >= 3400
 #if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
@@ -56,7 +56,7 @@ sbitmap_verify_popcount (const_sbitmap a)
 {
   unsigned ix;
   unsigned int lastword;
-  
+
   if (!a->popcount)
     return;
 
@@ -80,7 +80,7 @@ sbitmap_alloc (unsigned int n_elms)
   bytes = size * sizeof (SBITMAP_ELT_TYPE);
   amt = (sizeof (struct simple_bitmap_def)
         + bytes - sizeof (SBITMAP_ELT_TYPE));
-  bmap = xmalloc (amt);
+  bmap = (sbitmap) xmalloc (amt);
   bmap->n_bits = n_elms;
   bmap->size = size;
   bmap->popcount = NULL;
@@ -92,8 +92,8 @@ sbitmap_alloc (unsigned int n_elms)
 sbitmap
 sbitmap_alloc_with_popcount (unsigned int n_elms)
 {
-  sbitmap const bmap = sbitmap_alloc (n_elms);  
-  bmap->popcount = xmalloc (bmap->size * sizeof (unsigned char));
+  sbitmap const bmap = sbitmap_alloc (n_elms);
+  bmap->popcount = XNEWVEC (unsigned char, bmap->size);
   return bmap;
 }
 
@@ -113,17 +113,16 @@ sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
     {
       amt = (sizeof (struct simple_bitmap_def)
            + bytes - sizeof (SBITMAP_ELT_TYPE));
-      bmap = xrealloc (bmap, amt);
+      bmap = (sbitmap) xrealloc (bmap, amt);
       if (bmap->popcount)
-       bmap->popcount = xrealloc (bmap->popcount,
-                                  size * sizeof (unsigned char));
+       bmap->popcount = XRESIZEVEC (unsigned char, bmap->popcount, size);
     }
 
   if (n_elms > bmap->n_bits)
     {
       if (def)
        {
-         memset (bmap->elms + bmap->size, -1, 
+         memset (bmap->elms + bmap->size, -1,
                  bytes - SBITMAP_SIZE_BYTES (bmap));
 
          /* Set the new bits if the original last element.  */
@@ -140,13 +139,13 @@ sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
        }
       else
        {
-         memset (bmap->elms + bmap->size, 0, 
+         memset (bmap->elms + bmap->size, 0,
                  bytes - SBITMAP_SIZE_BYTES (bmap));
          if (bmap->popcount)
            memset (bmap->popcount + bmap->size, 0,
-                   (size * sizeof (unsigned char)) 
+                   (size * sizeof (unsigned char))
                    - (bmap->size * sizeof (unsigned char)));
-                   
+
        }
     }
   else if (n_elms < bmap->n_bits)
@@ -219,7 +218,7 @@ sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
   }
 
   amt = vector_bytes + (n_vecs * elm_bytes);
-  bitmap_vector = xmalloc (amt);
+  bitmap_vector = (sbitmap *) xmalloc (amt);
 
   for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
     {
@@ -249,7 +248,7 @@ sbitmap_copy (sbitmap dst, const_sbitmap src)
 void
 sbitmap_copy_n (sbitmap dst, const_sbitmap src, unsigned int n)
 {
-  memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n);  
+  memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n);
   if (dst->popcount)
     memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * n);
 }
@@ -274,6 +273,57 @@ sbitmap_empty_p (const_sbitmap bmap)
   return true;
 }
 
+/* Return false if any of the N bits are set in MAP starting at
+   START.  */
+
+bool
+sbitmap_range_empty_p (const_sbitmap bmap, unsigned int start, unsigned int n)
+{
+  unsigned int i = start / SBITMAP_ELT_BITS;
+  SBITMAP_ELT_TYPE elm;
+  unsigned int shift = start % SBITMAP_ELT_BITS;
+
+  gcc_assert (bmap->n_bits >= start + n);
+
+  elm = bmap->elms[i];
+  elm = elm >> shift;
+
+  if (shift + n <= SBITMAP_ELT_BITS)
+    {
+      /* The bits are totally contained in a single element.  */
+      if (shift + n < SBITMAP_ELT_BITS)
+        elm &= ((1 << n) - 1);
+      return (elm == 0);
+    }
+
+  if (elm)
+    return false;
+
+  n -= SBITMAP_ELT_BITS - shift;
+  i++;
+
+  /* Deal with full elts.  */
+  while (n >= SBITMAP_ELT_BITS)
+    {
+      if (bmap->elms[i])
+       return false;
+      i++;
+      n -= SBITMAP_ELT_BITS;
+    }
+
+  /* The leftover bits.  */
+  if (n)
+    {
+      elm = bmap->elms[i];
+      elm &= ((1 << n) - 1);
+      return (elm == 0);
+    }
+
+  return true;
+}
+
+
+
 /* Zero all elements in a bitmap.  */
 
 void
@@ -301,7 +351,7 @@ sbitmap_ones (sbitmap bmap)
       bmap->elms[bmap->size - 1]
        = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
       if (bmap->popcount)
-       bmap->popcount[bmap->size - 1] 
+       bmap->popcount[bmap->size - 1]
          = do_popcount (bmap->elms[bmap->size - 1]);
     }
 }
@@ -343,7 +393,7 @@ sbitmap_union_of_diff_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_s
   SBITMAP_ELT_TYPE changed = 0;
 
   gcc_assert (!dst->popcount);
-  
+
   for (i = 0; i < n; i++)
     {
       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
@@ -380,7 +430,7 @@ sbitmap_not (sbitmap dst, const_sbitmap src)
   const_sbitmap_ptr srcp = src->elms;
   unsigned int last_bit;
 
-  gcc_assert (!dst->popcount);  
+  gcc_assert (!dst->popcount);
 
   for (i = 0; i < n; i++)
     *dstp++ = ~*srcp++;
@@ -482,7 +532,7 @@ sbitmap_a_and_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
          if (wordchanged)
            *popcountp = do_popcount (tmp);
          popcountp++;
-       }      
+       }
       *dstp++ = tmp;
     }
 #ifdef BITMAP_DEBUGGING
@@ -502,7 +552,7 @@ sbitmap_a_xor_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
   const_sbitmap_ptr ap = a->elms;
   const_sbitmap_ptr bp = b->elms;
   SBITMAP_ELT_TYPE changed = 0;
-  
+
   gcc_assert (!dst->popcount);
 
   for (i = 0; i < n; i++)
@@ -534,7 +584,7 @@ sbitmap_a_xor_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
          if (wordchanged)
            *popcountp = do_popcount (tmp);
          popcountp++;
-       } 
+       }
       *dstp++ = tmp;
     }
 #ifdef BITMAP_DEBUGGING
@@ -586,7 +636,7 @@ sbitmap_a_or_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
          if (wordchanged)
            *popcountp = do_popcount (tmp);
          popcountp++;
-       } 
+       }
       *dstp++ = tmp;
     }
 #ifdef BITMAP_DEBUGGING
@@ -707,7 +757,7 @@ sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb)
       e = EDGE_SUCC (b, ix);
       if (e->dest == EXIT_BLOCK_PTR)
        continue;
-      
+
       sbitmap_copy (dst, src[e->dest->index]);
       break;
     }
@@ -1012,7 +1062,7 @@ sbitmap_popcount (const_sbitmap a, unsigned long maxbit)
 
   if (maxbit == 0)
     return 0;
-  
+
   if (maxbit >= a->n_bits)
     maxbit = a->n_bits;