[5/5] Don't mark live recursively in gt_cleare_cache

[PATCH 5/5] Don't mark live recursively in gt_cleare_cache

2015-07-10  Tom de Vries  <tom@codesourcery.com>

	PR libgomp/66714
	* hash-table.h (gt_cleare_cache): Mark cache entry non-recursively.
	(gt_cleare_cache) [ENABLE_CHECKING]: Assert non-key components of live
	entry already marked.  Assert dead key component implies dead entry.
	* tree.h (struct tree_decl_map_cache_hasher) [ENABLE_CHECKING]: Add new
	function ggc_marked_nonkey_p.
	* tree.c (struct tree_vec_map_cache_hasher) [ENABLE_CHECKING]: Same.
	* ubsan.c (struct tree_type_map_cache_hasher) [ENABLE_CHECKING]: Same.
	* varasm.c (struct tm_clone_hasher) [ENABLE_CHECKING]: Same.
	* hash-traits.h (struct ggc_cache_remove) [ENABLE_CHECKING]: Same.
	* trans-mem.c (struct tm_wrapper_hasher) [ENABLE_CHECKING]: Same.

	* testsuite/libgomp.c/pr66714.c: New test.
---
 gcc/hash-table.h                      | 64 +++++++++++++++++++++++++++++++++--
 gcc/hash-traits.h                     |  4 +++
 gcc/trans-mem.c                       |  6 ++++
 gcc/tree.c                            |  6 ++++
 gcc/tree.h                            |  6 ++++
 gcc/ubsan.c                           |  6 ++++
 gcc/varasm.c                          |  6 ++++
 libgomp/testsuite/libgomp.c/pr66714.c | 17 ++++++++++
 8 files changed, 113 insertions(+), 2 deletions(-)
 create mode 100644 libgomp/testsuite/libgomp.c/pr66714.c

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 12e0c96..282ba8a 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -1046,14 +1046,74 @@  gt_cleare_cache (hash_table<H> *h)
   if (!h)
     return;
 
+  /* There are roughly 2 types of cache entries.
+
+     I.
+
+     The simple one, that uses ggc_cache_remove::keep_cache_entry.
+
+       int keep_cache_entry (T &e) { return ggc_marked_p (e) ? -1 : 0; }
+
+     The function returns either live (-1) or dead (0), dependent on whether the
+     entry was marked during the marking phase.
+
+     If the entry is dead, we clear the slot holding the entry.  The slot can be
+     now be reused, and the entry will be freed during the sweeping phase.
+
+     If the entry is live we're done.  The entry itself, and anything reachable
+     from the entry have been marked during the marking phase.
+
+
+     II.
+
+     The complex one, with a non-standard keep_cache_entry.
+
+     Say we have a cache entry E with key field to and non-key field from:
+
+       struct sE {
+	 type1 from;
+	 type2 to;
+       };
+       typedef struct sE *E;
+
+     and a keep_cache_entry function:
+
+       int keep_cache_entry (E &e) { return ggc_marked_p (e->from); }
+
+     The function returns either live (1) or dead (0), dependent on whether the
+     from field of the entry was marked during the marking phase.
+
+     If the from field is dead, we clear the slot holding the entry.  The slot
+     can be now be reused, and the from field will be freed during the sweeping
+     phase.  The to field will be freed during the sweeping phase dependent on
+     whether it was marked live during the marking phase.  Furthermore, we check
+     that the entry was not marked.  If that that check fails, it means that
+     we ended up with a live entry with a dead from field.
+
+     If the from field is live, we mark the entry non-recursively live, since
+     the cache may hold the only reference to the entry.
+     However, we check that anything reachable from the entry has already been
+     marked during the marking phase.  If that that check fails, it means that
+     we ended up with a live entry with a dead to field.  */
+
   for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
     if (!table::is_empty (*iter) && !table::is_deleted (*iter))
       {
 	int res = H::keep_cache_entry (*iter);
 	if (res == 0)
-	  h->clear_slot (&*iter);
+	  {
+#ifdef ENABLE_CHECKING
+	    gcc_assert (!ggc_marked_p (*iter));
+#endif
+	    h->clear_slot (&*iter);
+	  }
 	else if (res != -1)
-	  gt_ggc_mx (*iter);
+	  {
+	    ggc_set_mark (*iter);
+#ifdef ENABLE_CHECKING
+	    gcc_assert (H::ggc_marked_nonkey_p (*iter));
+#endif
+	  }
       }
 }
 
diff --git a/gcc/hash-traits.h b/gcc/hash-traits.h
index 450354a..9c0ff65 100644
--- a/gcc/hash-traits.h
+++ b/gcc/hash-traits.h
@@ -241,6 +241,10 @@  struct ggc_cache_remove : ggc_remove<T>
   /* Entries are weakly held because this is for caches.  */
   static void ggc_mx (T &) {}
 
+#ifdef ENABLE_CHECKING
+  static int ggc_marked_nonkey_p (T &) { return 1; }
+#endif
+
   static int
   keep_cache_entry (T &e)
   {
diff --git a/gcc/trans-mem.c b/gcc/trans-mem.c
index c809a2e..70432f3 100644
--- a/gcc/trans-mem.c
+++ b/gcc/trans-mem.c
@@ -478,6 +478,12 @@  struct tm_wrapper_hasher : ggc_cache_ptr_hash<tree_map>
     return a->base.from == b->base.from;
   }
 
+#ifdef ENABLE_CHECKING
+  static int ggc_marked_nonkey_p (tree_map *&m) {
+    return ggc_marked_p (m->to);
+  }
+#endif
+
   static int
   keep_cache_entry (tree_map *&m)
   {
diff --git a/gcc/tree.c b/gcc/tree.c
index bb4467d..fbcb37d 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -271,6 +271,12 @@  struct tree_vec_map_cache_hasher : ggc_cache_ptr_hash<tree_vec_map>
     return a->base.from == b->base.from;
   }
 
+#ifdef ENABLE_CHECKING
+  static int ggc_marked_nonkey_p (tree_vec_map *&m) {
+    return ggc_marked_p (m->to);
+  }
+#endif
+
   static int
   keep_cache_entry (tree_vec_map *&m)
   {
diff --git a/gcc/tree.h b/gcc/tree.h
index 8d8fb7e..c100c365 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -4635,6 +4635,12 @@  struct tree_decl_map_cache_hasher : ggc_cache_ptr_hash<tree_decl_map>
     return tree_decl_map_eq (a, b);
   }
 
+#ifdef ENABLE_CHECKING
+  static int ggc_marked_nonkey_p (tree_decl_map *&m) {
+    return ggc_marked_p (m->to);
+  }
+#endif
+
   static int
   keep_cache_entry (tree_decl_map *&m)
   {
diff --git a/gcc/ubsan.c b/gcc/ubsan.c
index 19eafab..350ad22 100644
--- a/gcc/ubsan.c
+++ b/gcc/ubsan.c
@@ -95,6 +95,12 @@  struct tree_type_map_cache_hasher : ggc_cache_ptr_hash<tree_type_map>
     return a->type.from == b->type.from;
   }
 
+#ifdef ENABLE_CHECKING
+   static int ggc_marked_nonkey_p (tree_type_map *&m) {
+     return ggc_marked_p (m->decl);
+  }
+#endif
+
   static int
   keep_cache_entry (tree_type_map *&m)
   {
diff --git a/gcc/varasm.c b/gcc/varasm.c
index 3e76032..4e44c43 100644
--- a/gcc/varasm.c
+++ b/gcc/varasm.c
@@ -5793,6 +5793,12 @@  struct tm_clone_hasher : ggc_cache_ptr_hash<tree_map>
   static hashval_t hash (tree_map *m) { return tree_map_hash (m); }
   static bool equal (tree_map *a, tree_map *b) { return tree_map_eq (a, b); }
 
+#ifdef ENABLE_CHECKING
+  static int ggc_marked_nonkey_p (tree_map *&m) {
+    return ggc_marked_p (m->to);
+  }
+#endif
+
   static int
   keep_cache_entry (tree_map *&e)
   {
diff --git a/libgomp/testsuite/libgomp.c/pr66714.c b/libgomp/testsuite/libgomp.c/pr66714.c
new file mode 100644
index 0000000..a8c5bbdb
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c/pr66714.c
@@ -0,0 +1,17 @@ 
+/* { dg-do "compile" } */
+/* { dg-additional-options "--param ggc-min-expand=0" } */
+/* { dg-additional-options "--param ggc-min-heapsize=0" } */
+/* { dg-additional-options "-g" } */
+
+/* Minimized from target-2.c.  */
+
+void
+fn3 (int x)
+{
+  double b[3 * x];
+  int i;
+  #pragma omp target
+    #pragma omp parallel for
+      for (i = 0; i < x; i++)
+	b[i] += 1;
+}
-- 
1.9.1