2008-05-22 Basile Starynkevitch <basile@starynkevitch.net>

	MELT branch merged with trunk r135793



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/melt-branch@135794 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 150 insertions, 1 deletions

diff --git a/gcc/ggc-zone.c b/gcc/ggc-zone.c
index e8185a06381..af211ad90dc 100644
--- a/gcc/ggc-zone.c
+++ b/gcc/ggc-zone.c
@@ -1,5 +1,5 @@
 /* "Bag-of-pages" zone garbage collector for the GNU compiler.
-   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007
+   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008
    Free Software Foundation, Inc.
 
    Contributed by Richard Henderson (rth@redhat.com) and Daniel Berlin
@@ -506,6 +506,47 @@ lookup_page_table_entry (const void *p)
   return base[L1][L2];
 }
 
+/* Traverse the page table and find the entry for a page.
+   Return NULL if the object wasn't allocated via the GC.  */
+
+static inline page_entry *
+lookup_page_table_if_allocated (const void *p)
+{
+  page_entry ***base;
+  size_t L1, L2;
+
+#if HOST_BITS_PER_PTR <= 32
+  base = &G.lookup[0];
+#else
+  page_table table = G.lookup;
+  size_t high_bits = (size_t) p & ~ (size_t) 0xffffffff;
+  while (1)
+    {
+      if (table == NULL)
+	return NULL;
+      if (table->high_bits == high_bits)
+	break;
+      table = table->next;
+    }
+  base = &table->table[0];
+#endif
+
+  /* Extract the level 1 and 2 indices.  */
+  L1 = LOOKUP_L1 (p);
+  if (! base[L1])
+    return NULL;
+
+  L2 = LOOKUP_L2 (p);
+  if (L2 >= PAGE_L2_SIZE)
+    return NULL;
+  /* We might have a page entry which does not correspond exactly to a
+     system page.  */
+  if (base[L1][L2] && (char *) p < base[L1][L2]->page)
+    return NULL;
+
+  return base[L1][L2];
+}
+
 /* Set the page table entry for the page that starts at P.  If ENTRY
    is NULL, clear the entry.  */
 
@@ -680,6 +721,55 @@ zone_find_object_size (struct small_page_entry *page,
 			     max_size);
 }
 
+/* highest_bit assumes that alloc_type is 32 bits.  */
+extern char check_alloc_type_size[(sizeof (alloc_type) == 4) ? 1 : -1];
+
+/* Find the highest set bit in VALUE.  Returns the bit number of that
+   bit, using the same values as ffs.  */
+static inline alloc_type
+highest_bit (alloc_type value)
+{
+  /* This also assumes that alloc_type is unsigned.  */
+  value |= value >> 1;
+  value |= value >> 2;
+  value |= value >> 4;
+  value |= value >> 8;
+  value |= value >> 16;
+  value = value ^ (value >> 1);
+  return alloc_ffs (value);
+}
+
+/* Find the offset from the start of an object to P, which may point
+   into the interior of the object.  */
+
+static unsigned long
+zone_find_object_offset (alloc_type *alloc_bits, size_t start_word,
+			 size_t start_bit)
+{
+  unsigned int offset_in_bits;
+  alloc_type alloc_word = alloc_bits[start_word];
+
+  /* Mask off any bits after the initial bit, but make sure to include
+     the initial bit in the result.  Note that START_BIT is
+     0-based.  */
+  if (start_bit < 8 * sizeof (alloc_type) - 1)
+    alloc_word &= (1 << (start_bit + 1)) - 1;
+  offset_in_bits = start_bit;
+
+  /* Search for the start of the object.  */
+  while (alloc_word == 0 && start_word > 0)
+    {
+      alloc_word = alloc_bits[--start_word];
+      offset_in_bits += 8 * sizeof (alloc_type);
+    }
+  /* We must always find a set bit.  */
+  gcc_assert (alloc_word != 0);
+  /* Note that the result of highest_bit is 1-based.  */
+  offset_in_bits -= highest_bit (alloc_word) - 1;
+
+  return BYTES_PER_ALLOC_BIT * offset_in_bits;
+}
+
 /* Allocate the mark bits for every zone, and set the pointers on each
    page.  */
 static void
@@ -1353,6 +1443,65 @@ ggc_free (void *p)
     }
 }
 
+/* Mark function for strings.  */
+
+void
+gt_ggc_m_S (const void *p)
+{
+  page_entry *entry;
+  unsigned long offset;
+
+  if (!p)
+    return;
+
+  /* Look up the page on which the object is alloced.  .  */
+  entry = lookup_page_table_if_allocated (p);
+  if (! entry)
+    return;
+
+  if (entry->pch_p)
+    {
+      size_t alloc_word, alloc_bit, t;
+      t = ((const char *) p - pch_zone.page) / BYTES_PER_ALLOC_BIT;
+      alloc_word = t / (8 * sizeof (alloc_type));
+      alloc_bit = t % (8 * sizeof (alloc_type));
+      offset = zone_find_object_offset (pch_zone.alloc_bits, alloc_word,
+					alloc_bit);
+    }
+  else if (entry->large_p)
+    {
+      struct large_page_entry *le = (struct large_page_entry *) entry;
+      offset = ((const char *) p) - entry->page;
+      gcc_assert (offset < le->bytes);
+    }
+  else
+    {
+      struct small_page_entry *se = (struct small_page_entry *) entry;
+      unsigned int start_word = zone_get_object_alloc_word (p);
+      unsigned int start_bit = zone_get_object_alloc_bit (p);
+      offset = zone_find_object_offset (se->alloc_bits, start_word, start_bit);
+
+      /* On some platforms a char* will not necessarily line up on an
+	 allocation boundary, so we have to update the offset to
+	 account for the leftover bytes.  */
+      offset += (size_t) p % BYTES_PER_ALLOC_BIT;
+    }
+
+  if (offset)
+    {
+      /* Here we've seen a char* which does not point to the beginning
+	 of an allocated object.  We assume it points to the middle of
+	 a STRING_CST.  */
+      gcc_assert (offset == offsetof (struct tree_string, str));
+      p = ((const char *) p) - offset;
+      gt_ggc_mx_lang_tree_node ((void *) p);
+      return;
+    }
+
+  /* Inefficient, but also unlikely to matter.  */
+  ggc_set_mark (p);
+}
+
 /* If P is not marked, mark it and return false.  Otherwise return true.
    P must have been allocated by the GC allocator; it mustn't point to
    static objects, stack variables, or memory allocated with malloc.  */