[RFC] two-phase marking in gt_cleare_cache

[RFC] two-phase marking in gt_cleare_cache

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 683 bytes --]

Hi,

Using attached untested patch, I managed to minimize a test-case failure 
for PR 66714.

The patch introduces two-phase marking in gt_cleare_cache:
- first phase, it loops over all the hash table entries and removes
   those which are dead
- second phase, it runs over all the live hash table entries and marks
   live items that are reachable from those live entries

By doing so, we make the behaviour of gt_cleare_cache independent of the 
order in which the entries are visited, turning:
- hard-to-trigger bugs which trigger for one visiting order but not for
   another, into
- more easily triggered bugs which trigger for any visiting order.

Any comments?

Thanks,
- Tom

[-- Attachment #2: 0001-Add-checking-in-gt_cleare_cache.patch --]
[-- Type: text/x-patch, Size: 1848 bytes --]

Add checking in gt_cleare_cache

---
 gcc/hash-table.h | 32 +++++++++++++++++++++++++++++++-
 1 file changed, 31 insertions(+), 1 deletion(-)

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 12e0c96..c2ea112 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -1046,7 +1046,37 @@ gt_cleare_cache (hash_table<H> *h)
   if (!h)
     return;
 
-  for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
+  typename table::iterator iter;
+
+#ifdef CHECKING
+  /* Say we have:
+     1. cache entry A, with keep_change_entry (A) == 1, and
+     2. cache entry B, with keep_change_entry (B) == 0, and
+     3. gt_ggc_mx (A) marks things live in such a way that keep_change_entry (B)
+        becomes 1.
+
+     In the loop at the end of the function, if A is visited first, then B is
+     kept.  If B is visited first, it is deleted.
+
+     We don't want the situation that the result of this function is dependent
+     on the order in which the entries are visited, so we consider this
+     situation a bug.
+
+     In order to stabilize the result of the function in presence of the bug, we
+     first clear all entries E with keep_change_entry (E) == 0.  By doing so, we
+     also maximize the impact of the liveness analysis done up until now, which
+     we hope makes it more likely that we run into bugs regarding that analysis.
+     We only do this when checking since it's more expensive.  */
+  for (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);
+      }
+#endif
+
+  for (iter = h->begin (); iter != h->end (); ++iter)
     if (!table::is_empty (*iter) && !table::is_deleted (*iter))
       {
 	int res = H::keep_cache_entry (*iter);
-- 
1.9.1

Re: [RFC] two-phase marking in gt_cleare_cache

[Richard Biener]

On Mon, Jul 6, 2015 at 10:57 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> Hi,
>
> Using attached untested patch, I managed to minimize a test-case failure for
> PR 66714.
>
> The patch introduces two-phase marking in gt_cleare_cache:
> - first phase, it loops over all the hash table entries and removes
>   those which are dead
> - second phase, it runs over all the live hash table entries and marks
>   live items that are reachable from those live entries
>
> By doing so, we make the behaviour of gt_cleare_cache independent of the
> order in which the entries are visited, turning:
> - hard-to-trigger bugs which trigger for one visiting order but not for
>   another, into
> - more easily triggered bugs which trigger for any visiting order.
>
> Any comments?

I think it is only half-way correct in your proposed change.  You only
fix the issue for hashes of the same kind.  To truly fix the issue you'd
have to change generated code for gt_clear_caches () and provide
a clearing-only implementation (or pass a operation mode bool to
the core worker in hash-table.h).

Thanks,
Richard.

> Thanks,
> - Tom

Re: [RFC] two-phase marking in gt_cleare_cache

[Richard Biener]

On Mon, Jul 6, 2015 at 3:25 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Jul 6, 2015 at 10:57 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> Hi,
>>
>> Using attached untested patch, I managed to minimize a test-case failure for
>> PR 66714.
>>
>> The patch introduces two-phase marking in gt_cleare_cache:
>> - first phase, it loops over all the hash table entries and removes
>>   those which are dead
>> - second phase, it runs over all the live hash table entries and marks
>>   live items that are reachable from those live entries
>>
>> By doing so, we make the behaviour of gt_cleare_cache independent of the
>> order in which the entries are visited, turning:
>> - hard-to-trigger bugs which trigger for one visiting order but not for
>>   another, into
>> - more easily triggered bugs which trigger for any visiting order.
>>
>> Any comments?
>
> I think it is only half-way correct in your proposed change.  You only
> fix the issue for hashes of the same kind.  To truly fix the issue you'd
> have to change generated code for gt_clear_caches () and provide
> a clearing-only implementation (or pass a operation mode bool to
> the core worker in hash-table.h).

Hmm, and don't we rather want to first mark and _then_ clear?  Because
if entry B in the hash is live and would keep A live then A _is_ kept in the
end but you'll remove it from the hash, possibly no longer using a still
live copy.

Richard.

> Thanks,
> Richard.
>
>> Thanks,
>> - Tom

Re: [RFC] two-phase marking in gt_cleare_cache

[Tom de Vries]

On 06/07/15 15:29, Richard Biener wrote:
> On Mon, Jul 6, 2015 at 3:25 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Mon, Jul 6, 2015 at 10:57 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>>> Hi,
>>>
>>> Using attached untested patch, I managed to minimize a test-case failure for
>>> PR 66714.
>>>
>>> The patch introduces two-phase marking in gt_cleare_cache:
>>> - first phase, it loops over all the hash table entries and removes
>>>    those which are dead
>>> - second phase, it runs over all the live hash table entries and marks
>>>    live items that are reachable from those live entries
>>>
>>> By doing so, we make the behaviour of gt_cleare_cache independent of the
>>> order in which the entries are visited, turning:
>>> - hard-to-trigger bugs which trigger for one visiting order but not for
>>>    another, into
>>> - more easily triggered bugs which trigger for any visiting order.
>>>
>>> Any comments?
>>
>> I think it is only half-way correct in your proposed change.  You only
>> fix the issue for hashes of the same kind.  To truly fix the issue you'd
>> have to change generated code for gt_clear_caches () and provide
>> a clearing-only implementation (or pass a operation mode bool to
>> the core worker in hash-table.h).
>

[ Btw, we have been discussing a similar issue before: 
https://gcc.gnu.org/ml/gcc/2010-07/msg00077.html ]

True, the problem exists at the scope of all variables marked with 
'cache', and this patch addresses the problem only within a single variable.

> Hmm, and don't we rather want to first mark and _then_ clear?

I. In favor of first clear and then mark:

It allows for:
- a lazy one phase implementation for !ENABLE_CHECKING where
   you do a single clear-or-mark phase (so the clear is lazy).
- an eager two phase implementation for ENABLE_CHECKING (where the
   clear is eager)
The approach of first a marking phase and then a clearing phase means 
you always have to do these two phases (you can't do the marking lazily).

First mark and then clear means the marking should be done iteratively. 
Each time you mark something live, another entry in another hash table 
could become live. Marking iteratively could become quite costly.

II. In favor of first mark and then clear:

The users of garbage collection will need to be less precise.

> Because
> if entry B in the hash is live and would keep A live then A _is_ kept in the
> end but you'll remove it from the hash, possibly no longer using a still
> live copy.
>

I'm not sure I understand the scenario you're concerned about, but ... 
say we have
- entry B: item B -> item A
- entry A: item A -> item Z

If you do clear first and mark second, and you start out with item B 
live and item A dead:
- during the clearing phase you clear entry A and keep entry B, and
- during the marking phase you mark item A live.

So we no longer have entry A, but item A is kept and entry B is kept.

Thanks,
- Tom

Re: [RFC] two-phase marking in gt_cleare_cache

[Richard Biener]

On Mon, Jul 6, 2015 at 7:29 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 06/07/15 15:29, Richard Biener wrote:
>>
>> On Mon, Jul 6, 2015 at 3:25 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>>
>>> On Mon, Jul 6, 2015 at 10:57 AM, Tom de Vries <Tom_deVries@mentor.com>
>>> wrote:
>>>>
>>>> Hi,
>>>>
>>>> Using attached untested patch, I managed to minimize a test-case failure
>>>> for
>>>> PR 66714.
>>>>
>>>> The patch introduces two-phase marking in gt_cleare_cache:
>>>> - first phase, it loops over all the hash table entries and removes
>>>>    those which are dead
>>>> - second phase, it runs over all the live hash table entries and marks
>>>>    live items that are reachable from those live entries
>>>>
>>>> By doing so, we make the behaviour of gt_cleare_cache independent of the
>>>> order in which the entries are visited, turning:
>>>> - hard-to-trigger bugs which trigger for one visiting order but not for
>>>>    another, into
>>>> - more easily triggered bugs which trigger for any visiting order.
>>>>
>>>> Any comments?
>>>
>>>
>>> I think it is only half-way correct in your proposed change.  You only
>>> fix the issue for hashes of the same kind.  To truly fix the issue you'd
>>> have to change generated code for gt_clear_caches () and provide
>>> a clearing-only implementation (or pass a operation mode bool to
>>> the core worker in hash-table.h).
>>
>>
>
> [ Btw, we have been discussing a similar issue before:
> https://gcc.gnu.org/ml/gcc/2010-07/msg00077.html ]
>
> True, the problem exists at the scope of all variables marked with 'cache',
> and this patch addresses the problem only within a single variable.
>
>> Hmm, and don't we rather want to first mark and _then_ clear?
>
>
> I. In favor of first clear and then mark:
>
> It allows for:
> - a lazy one phase implementation for !ENABLE_CHECKING where
>   you do a single clear-or-mark phase (so the clear is lazy).
> - an eager two phase implementation for ENABLE_CHECKING (where the
>   clear is eager)
> The approach of first a marking phase and then a clearing phase means you
> always have to do these two phases (you can't do the marking lazily).

True.

> First mark and then clear means the marking should be done iteratively. Each
> time you mark something live, another entry in another hash table could
> become live. Marking iteratively could become quite costly.

I don't see this - marking is done recursively so if one entry makes another
live and that makes another live the usual GC marking recursion will deal
with this?

> II. In favor of first mark and then clear:
>
> The users of garbage collection will need to be less precise.
>
>> Because
>> if entry B in the hash is live and would keep A live then A _is_ kept in
>> the
>> end but you'll remove it from the hash, possibly no longer using a still
>> live copy.
>>
>
> I'm not sure I understand the scenario you're concerned about, but ... say
> we have
> - entry B: item B -> item A
> - entry A: item A -> item Z
>
> If you do clear first and mark second, and you start out with item B live
> and item A dead:
> - during the clearing phase you clear entry A and keep entry B, and
> - during the marking phase you mark item A live.
>
> So we no longer have entry A, but item A is kept and entry B is kept.

Yes.  This makes the cache weaker in that after this GC operation
a lookup of A no longer succeeds but it still is there.

The whole point of your patch was to make the behavior more predictable
and in some way it succeeds (within a cache).  As it is supposed to
put more stress on the cache logic (it's ENABLE_CHECKING only)
it makes sense to clear optimistically (after all it's a cache and not
guaranteed to find a still live entry).  It would be still nice to cover
all caches together because as I remember we've mostly seen issues
of caches interacting.

Richard.

> Thanks,
> - Tom
>

Re: [RFC] two-phase marking in gt_cleare_cache

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 4567 bytes --]

On 07/07/15 10:42, Richard Biener wrote:
> On Mon, Jul 6, 2015 at 7:29 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> On 06/07/15 15:29, Richard Biener wrote:
>>>
>>> On Mon, Jul 6, 2015 at 3:25 PM, Richard Biener
>>> <richard.guenther@gmail.com> wrote:
>>>>
>>>> On Mon, Jul 6, 2015 at 10:57 AM, Tom de Vries <Tom_deVries@mentor.com>
>>>> wrote:
>>>>>
>>>>> Hi,
>>>>>
>>>>> Using attached untested patch, I managed to minimize a test-case failure
>>>>> for
>>>>> PR 66714.
>>>>>
>>>>> The patch introduces two-phase marking in gt_cleare_cache:
>>>>> - first phase, it loops over all the hash table entries and removes
>>>>>     those which are dead
>>>>> - second phase, it runs over all the live hash table entries and marks
>>>>>     live items that are reachable from those live entries
>>>>>
>>>>> By doing so, we make the behaviour of gt_cleare_cache independent of the
>>>>> order in which the entries are visited, turning:
>>>>> - hard-to-trigger bugs which trigger for one visiting order but not for
>>>>>     another, into
>>>>> - more easily triggered bugs which trigger for any visiting order.
>>>>>
>>>>> Any comments?
>>>>
>>>>
>>>> I think it is only half-way correct in your proposed change.  You only
>>>> fix the issue for hashes of the same kind.  To truly fix the issue you'd
>>>> have to change generated code for gt_clear_caches () and provide
>>>> a clearing-only implementation (or pass a operation mode bool to
>>>> the core worker in hash-table.h).
>>>
>>>
>>
>> [ Btw, we have been discussing a similar issue before:
>> https://gcc.gnu.org/ml/gcc/2010-07/msg00077.html ]
>>
>> True, the problem exists at the scope of all variables marked with 'cache',
>> and this patch addresses the problem only within a single variable.
>>
>>> Hmm, and don't we rather want to first mark and _then_ clear?
>>
>>
>> I. In favor of first clear and then mark:
>>
>> It allows for:
>> - a lazy one phase implementation for !ENABLE_CHECKING where
>>    you do a single clear-or-mark phase (so the clear is lazy).
>> - an eager two phase implementation for ENABLE_CHECKING (where the
>>    clear is eager)
>> The approach of first a marking phase and then a clearing phase means you
>> always have to do these two phases (you can't do the marking lazily).
>
> True.
>
>> First mark and then clear means the marking should be done iteratively. Each
>> time you mark something live, another entry in another hash table could
>> become live. Marking iteratively could become quite costly.
>
> I don't see this - marking is done recursively so if one entry makes another
> live and that makes another live the usual GC marking recursion will deal
> with this?
>

That is not my understanding.  Marking an item live doesn't mean that 
the associated cache entries become live. For that, we have to iterate 
again over all hash tables and all entries to find those entries.
And by marking those, we may find new items which are live. And the 
process starts over again, until fixed point.

[ If we maintain a per-item list of cache entries the item is the key 
for, then we can do this recursively, rather than iteratively. ]

>> II. In favor of first mark and then clear:
>>
>> The users of garbage collection will need to be less precise.
>>
>>> Because
>>> if entry B in the hash is live and would keep A live then A _is_ kept in
>>> the
>>> end but you'll remove it from the hash, possibly no longer using a still
>>> live copy.
>>>
>>
>> I'm not sure I understand the scenario you're concerned about, but ... say
>> we have
>> - entry B: item B -> item A
>> - entry A: item A -> item Z
>>
>> If you do clear first and mark second, and you start out with item B live
>> and item A dead:
>> - during the clearing phase you clear entry A and keep entry B, and
>> - during the marking phase you mark item A live.
>>
>> So we no longer have entry A, but item A is kept and entry B is kept.
>
> Yes.  This makes the cache weaker in that after this GC operation
> a lookup of A no longer succeeds but it still is there.
>
> The whole point of your patch was to make the behavior more predictable
> and in some way it succeeds (within a cache).  As it is supposed to
> put more stress on the cache logic (it's ENABLE_CHECKING only)
> it makes sense to clear optimistically (after all it's a cache and not
> guaranteed to find a still live entry).  It would be still nice to cover
> all caches together because as I remember we've mostly seen issues
> of caches interacting.
>

Attached patch (completed no-bootstrap c-only build) implements that.

Thanks,
- Tom


[-- Attachment #2: 0001-Add-clear-phase-mark-phase-cache-clearing.patch --]
[-- Type: text/x-patch, Size: 5453 bytes --]

Add clear-phase/mark-phase cache clearing

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

	* gengtype.c (finish_cache_funcs): Add phase param to
	gt_clear_caches_<file> and gt_clear_caches.
	(write_roots): Add phase param to gt_clear_caches_<file>, and use.
	* ggc-common.c (ggc_mark_roots): Add arg to call to gt_clear_caches.
	Call gt_clear_caches twice for ENABLE_CHECKING.
	* ggc.h (gt_clear_caches): Add phase param to declaration.
	* hash-table.h (gt_cleare_cache): Add and handle phase param.
---
 gcc/gengtype.c   | 11 ++++++-----
 gcc/ggc-common.c | 11 ++++++++++-
 gcc/ggc.h        |  2 +-
 gcc/hash-table.h | 55 ++++++++++++++++++++++++++++++++++++++++++++-----------
 4 files changed, 61 insertions(+), 18 deletions(-)

diff --git a/gcc/gengtype.c b/gcc/gengtype.c
index 137e0ff..e138fd8 100644
--- a/gcc/gengtype.c
+++ b/gcc/gengtype.c
@@ -4211,12 +4211,13 @@ finish_cache_funcs (flist *flp)
 	    {
 	      oprintf (base_files[fnum], "extern void gt_clear_caches_");
 	      put_mangled_filename (base_files[fnum], fli2->file);
-	      oprintf (base_files[fnum], " ();\n");
+	      oprintf (base_files[fnum], " (unsigned int);\n");
 	    }
       }
 
   for (size_t fnum = 0; base_files && fnum < num_lang_dirs; fnum++)
-    oprintf (base_files[fnum], "void\ngt_clear_caches ()\n{\n");
+    oprintf (base_files[fnum],
+	     "void\ngt_clear_caches (unsigned int phase)\n{\n");
 
   for (fli2 = flp; fli2; fli2 = fli2->next)
     if (fli2->started_p)
@@ -4231,7 +4232,7 @@ finish_cache_funcs (flist *flp)
 	    {
 	      oprintf (base_files[fnum], "  gt_clear_caches_");
 	      put_mangled_filename (base_files[fnum], fli2->file);
-	      oprintf (base_files[fnum], " ();\n");
+	      oprintf (base_files[fnum], " (phase);\n");
 	    }
       }
 
@@ -4660,10 +4661,10 @@ write_roots (pair_p variables, bool emit_pch)
 
 	  oprintf (f, "void\ngt_clear_caches_");
 	  put_mangled_filename (f, v->line.file);
-	  oprintf (f, " ()\n{\n");
+	  oprintf (f, " (unsigned int phase)\n{\n");
 	}
 
-      oprintf (f, "  gt_cleare_cache (%s);\n", v->name);
+      oprintf (f, "  gt_cleare_cache (%s, phase);\n", v->name);
     }
 
   finish_cache_funcs (flp);
diff --git a/gcc/ggc-common.c b/gcc/ggc-common.c
index 5096837..4f7e383 100644
--- a/gcc/ggc-common.c
+++ b/gcc/ggc-common.c
@@ -100,7 +100,16 @@ ggc_mark_roots (void)
   if (ggc_protect_identifiers)
     ggc_mark_stringpool ();
 
-  gt_clear_caches ();
+#ifdef ENABLE_CHECKING
+  /* Phase 1: Clear.  */
+  gt_clear_caches (1);
+
+  /* Phase 2: Mark.  */
+  gt_clear_caches (2);
+#else
+  /* Phase 0: Mark or Clear.  */
+  gt_clear_caches (0);
+#endif
 
   if (! ggc_protect_identifiers)
     ggc_purge_stringpool ();
diff --git a/gcc/ggc.h b/gcc/ggc.h
index ebc6a5d..0f6ff85 100644
--- a/gcc/ggc.h
+++ b/gcc/ggc.h
@@ -54,7 +54,7 @@ extern int gt_pch_note_object (void *, void *, gt_note_pointers);
 extern void gt_pch_note_reorder (void *, void *, gt_handle_reorder);
 
 /* generated function to clear caches in gc memory.  */
-extern void gt_clear_caches ();
+extern void gt_clear_caches (unsigned int);
 
 /* Mark the object in the first parameter and anything it points to.  */
 typedef void (*gt_pointer_walker) (void *);
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 12e0c96..380e90f 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -491,7 +491,8 @@ private:
   template<typename T> friend void gt_pch_nx (hash_table<T> *,
 					      gt_pointer_operator, void *);
 
-  template<typename T> friend void gt_cleare_cache (hash_table<T> *);
+  template<typename T> friend void gt_cleare_cache (hash_table<T> *,
+						    unsigned int phase);
 
   value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
   value_type *find_empty_slot_for_expand (hashval_t);
@@ -1039,22 +1040,54 @@ gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
 
 template<typename H>
 inline void
-gt_cleare_cache (hash_table<H> *h)
+gt_cleare_cache (hash_table<H> *h, unsigned int phase)
 {
   extern void gt_ggc_mx (typename H::value_type &t);
   typedef hash_table<H> table;
   if (!h)
     return;
 
-  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);
-	else if (res != -1)
-	  gt_ggc_mx (*iter);
-      }
+  typename table::iterator iter;
+  switch (phase)
+    {
+    case 0:
+      /* Phase 0: Mark or Clear.  */
+      for (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);
+	    else if (res != -1)
+	      gt_ggc_mx (*iter);
+	  }
+      break;
+
+    case 1:
+      /* Phase 1: Clear.  */
+      for (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);
+	  }
+      break;
+
+    case 2:
+      /* Phase 2: Mark.  */
+      for (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 == 1)
+	      gt_ggc_mx (*iter);
+	  }
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
 }
 
 #endif /* TYPED_HASHTAB_H */
-- 
1.9.1

Re: [RFC] two-phase marking in gt_cleare_cache

[Richard Biener]

On Tue, Jul 7, 2015 at 11:39 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 07/07/15 10:42, Richard Biener wrote:
>>
>> On Mon, Jul 6, 2015 at 7:29 PM, Tom de Vries <Tom_deVries@mentor.com>
>> wrote:
>>>
>>> On 06/07/15 15:29, Richard Biener wrote:
>>>>
>>>>
>>>> On Mon, Jul 6, 2015 at 3:25 PM, Richard Biener
>>>> <richard.guenther@gmail.com> wrote:
>>>>>
>>>>>
>>>>> On Mon, Jul 6, 2015 at 10:57 AM, Tom de Vries <Tom_deVries@mentor.com>
>>>>> wrote:
>>>>>>
>>>>>>
>>>>>> Hi,
>>>>>>
>>>>>> Using attached untested patch, I managed to minimize a test-case
>>>>>> failure
>>>>>> for
>>>>>> PR 66714.
>>>>>>
>>>>>> The patch introduces two-phase marking in gt_cleare_cache:
>>>>>> - first phase, it loops over all the hash table entries and removes
>>>>>>     those which are dead
>>>>>> - second phase, it runs over all the live hash table entries and marks
>>>>>>     live items that are reachable from those live entries
>>>>>>
>>>>>> By doing so, we make the behaviour of gt_cleare_cache independent of
>>>>>> the
>>>>>> order in which the entries are visited, turning:
>>>>>> - hard-to-trigger bugs which trigger for one visiting order but not
>>>>>> for
>>>>>>     another, into
>>>>>> - more easily triggered bugs which trigger for any visiting order.
>>>>>>
>>>>>> Any comments?
>>>>>
>>>>>
>>>>>
>>>>> I think it is only half-way correct in your proposed change.  You only
>>>>> fix the issue for hashes of the same kind.  To truly fix the issue
>>>>> you'd
>>>>> have to change generated code for gt_clear_caches () and provide
>>>>> a clearing-only implementation (or pass a operation mode bool to
>>>>> the core worker in hash-table.h).
>>>>
>>>>
>>>>
>>>
>>> [ Btw, we have been discussing a similar issue before:
>>> https://gcc.gnu.org/ml/gcc/2010-07/msg00077.html ]
>>>
>>> True, the problem exists at the scope of all variables marked with
>>> 'cache',
>>> and this patch addresses the problem only within a single variable.
>>>
>>>> Hmm, and don't we rather want to first mark and _then_ clear?
>>>
>>>
>>>
>>> I. In favor of first clear and then mark:
>>>
>>> It allows for:
>>> - a lazy one phase implementation for !ENABLE_CHECKING where
>>>    you do a single clear-or-mark phase (so the clear is lazy).
>>> - an eager two phase implementation for ENABLE_CHECKING (where the
>>>    clear is eager)
>>> The approach of first a marking phase and then a clearing phase means you
>>> always have to do these two phases (you can't do the marking lazily).
>>
>>
>> True.
>>
>>> First mark and then clear means the marking should be done iteratively.
>>> Each
>>> time you mark something live, another entry in another hash table could
>>> become live. Marking iteratively could become quite costly.
>>
>>
>> I don't see this - marking is done recursively so if one entry makes
>> another
>> live and that makes another live the usual GC marking recursion will deal
>> with this?
>>
>
> That is not my understanding.  Marking an item live doesn't mean that the
> associated cache entries become live. For that, we have to iterate again
> over all hash tables and all entries to find those entries.
> And by marking those, we may find new items which are live. And the process
> starts over again, until fixed point.

All "used" predicates are basically ggc_marked_p () AFAIK.  So when sth
was not marked previosuly GC will recurse to marking it.  GC only considers
the reference from the cache special not references from entries in the cache.

But maybe I am missing something here.

> [ If we maintain a per-item list of cache entries the item is the key for,
> then we can do this recursively, rather than iteratively.
>
>>> II. In favor of first mark and then clear:
>>>
>>> The users of garbage collection will need to be less precise.
>>>
>>>> Because
>>>> if entry B in the hash is live and would keep A live then A _is_ kept in
>>>> the
>>>> end but you'll remove it from the hash, possibly no longer using a still
>>>> live copy.
>>>>
>>>
>>> I'm not sure I understand the scenario you're concerned about, but ...
>>> say
>>> we have
>>> - entry B: item B -> item A
>>> - entry A: item A -> item Z
>>>
>>> If you do clear first and mark second, and you start out with item B live
>>> and item A dead:
>>> - during the clearing phase you clear entry A and keep entry B, and
>>> - during the marking phase you mark item A live.
>>>
>>> So we no longer have entry A, but item A is kept and entry B is kept.
>>
>>
>> Yes.  This makes the cache weaker in that after this GC operation
>> a lookup of A no longer succeeds but it still is there.
>>
>> The whole point of your patch was to make the behavior more predictable
>> and in some way it succeeds (within a cache).  As it is supposed to
>> put more stress on the cache logic (it's ENABLE_CHECKING only)
>> it makes sense to clear optimistically (after all it's a cache and not
>> guaranteed to find a still live entry).  It would be still nice to cover
>> all caches together because as I remember we've mostly seen issues
>> of caches interacting.
>>
>
> Attached patch (completed no-bootstrap c-only build) implements that.

Looks good to me.

Thanks,
Richard.

> Thanks,
> - Tom
>

Re: [RFC] two-phase marking in gt_cleare_cache

[Michael Matz]

Hi,

On Mon, 6 Jul 2015, Richard Biener wrote:

> >> By doing so, we make the behaviour of gt_cleare_cache independent of the
> >> order in which the entries are visited, turning:
> >> - hard-to-trigger bugs which trigger for one visiting order but not for
> >>   another, into
> >> - more easily triggered bugs which trigger for any visiting order.
> >>
> >> Any comments?
> >
> > I think it is only half-way correct in your proposed change.  You only
> > fix the issue for hashes of the same kind.  To truly fix the issue you'd
> > have to change generated code for gt_clear_caches () and provide
> > a clearing-only implementation (or pass a operation mode bool to
> > the core worker in hash-table.h).
> 
> Hmm, and don't we rather want to first mark and _then_ clear?  Because 
> if entry B in the hash is live and would keep A live then A _is_ kept in 
> the end but you'll remove it from the hash, possibly no longer using a 
> still live copy.

I don't think such use has ever worked with the caching hash tables.  Even 
the old (before c++) scheme didn't iterate, i.e. if a cache-hash entry A
became life from outside, but it itself kept an entry B live in the hash 
table (with no other references to B) then this never worked (or only by 
luck), because the slot was always cleared if !ggc_marked_p, so if B was 
visited before A it was removed from the hash-table (and in particular B's 
gt_ggc_mx routine was never called, so whatever B needed wasn't even 
marked).

Given this I think the call to gt_ggc_mx is superfluous because it 
wouldn't work relyably for multi-step dependencies anyway.  Hence a 
situation that works with that call in place, and breaking without it is 
actually a bug waiting to be uncovered.


Ciao,
Michael.

Re: [RFC] two-phase marking in gt_cleare_cache

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 2628 bytes --]

On 07/07/15 16:00, Michael Matz wrote:
> Hi,
>
> On Mon, 6 Jul 2015, Richard Biener wrote:
>
>>>> By doing so, we make the behaviour of gt_cleare_cache independent of the
>>>> order in which the entries are visited, turning:
>>>> - hard-to-trigger bugs which trigger for one visiting order but not for
>>>>    another, into
>>>> - more easily triggered bugs which trigger for any visiting order.
>>>>
>>>> Any comments?
>>>
>>> I think it is only half-way correct in your proposed change.  You only
>>> fix the issue for hashes of the same kind.  To truly fix the issue you'd
>>> have to change generated code for gt_clear_caches () and provide
>>> a clearing-only implementation (or pass a operation mode bool to
>>> the core worker in hash-table.h).
>>
>> Hmm, and don't we rather want to first mark and _then_ clear?  Because
>> if entry B in the hash is live and would keep A live then A _is_ kept in
>> the end but you'll remove it from the hash, possibly no longer using a
>> still live copy.
>
> I don't think such use has ever worked with the caching hash tables.  Even
> the old (before c++) scheme didn't iterate, i.e. if a cache-hash entry A
> became life from outside, but it itself kept an entry B live in the hash
> table (with no other references to B) then this never worked (or only by
> luck), because the slot was always cleared if !ggc_marked_p, so if B was
> visited before A it was removed from the hash-table (and in particular B's
> gt_ggc_mx routine was never called, so whatever B needed wasn't even
> marked).
>
> Given this I think the call to gt_ggc_mx is superfluous because it
> wouldn't work relyably for multi-step dependencies anyway.  Hence a
> situation that works with that call in place, and breaking without it is
> actually a bug waiting to be uncovered.
>

Attached patch tries to get multi-step dependencies right, without using 
iteration-till-fixed-point.

During the marking phase, we do recursive marking of the cache entries, 
while skipping the marking of:
- the cache entry itself, and
- the key component of the cache entry.
This marking is done for all non-empty cache entries independent of the 
current value of keep_cache_entry. So we make a conservative choice 
here, and by doing so avoid having to iterate-till-fixed-point.

During the cache-clear phase, for each cache entry we either 
non-recursively mark it live, or remove it.

AFAIU, this scheme reliably handles multi-step dependencies and does not 
increase runtime.

Passes a minimal c build, and it fixes the ICE of PR66714 (although 
there still might be a root cause to address, I'm not sure).

Thanks,
- Tom


[-- Attachment #2: 0001-Use-conservative-non-iterative-strategy-for-caches.patch --]
[-- Type: text/x-patch, Size: 6156 bytes --]

Use conservative non-iterative strategy for caches

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

	PR libgomp/66714
	* hash-table.h (gt_cleare_cache): Don't recurse cache entries, just
	mark.
	* trans-mem.c (struct tm_wrapper_hasher::ggc_mx (tree_map *&m)): New
	function.
	* tree.c (struct tree_vec_map_cache_hasher::ggc_mx (tree_vec_map *&m):
	Same.
	* tree.h
	(struct tree_decl_map_cache_hasher::ggc_mx (tree_decl_map *&m)): Same.
	* ubsan.c
	(struct tree_type_map_cache_hasher::ggc_mx (tree_type_map *&m)): Same.
	* varasm.c (struct tm_clone_hasher::ggc_mx (tree_map *&m)): Same.

	* testsuite/libgomp.c/pr66714.c: New test.
---
 gcc/hash-table.h                      | 28 +++++++++++++++++++++++++++-
 gcc/trans-mem.c                       |  4 ++++
 gcc/tree.c                            |  7 +++++++
 gcc/tree.h                            |  6 ++++++
 gcc/ubsan.c                           |  4 ++++
 gcc/varasm.c                          |  4 ++++
 libgomp/testsuite/libgomp.c/pr66714.c | 17 +++++++++++++++++
 7 files changed, 69 insertions(+), 1 deletion(-)
 create mode 100644 libgomp/testsuite/libgomp.c/pr66714.c

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 12e0c96..ce899bd 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -1046,6 +1046,32 @@ gt_cleare_cache (hash_table<H> *h)
   if (!h)
     return;
 
+  /* Say we have a cache entry E with key 'from' and non-key 'to'.
+
+     The marking of non-key 'to' should be done in ggc_mx () during the marking
+     phase.  We mark the non-key 'to' conservatively, that is, regardless of
+     whether the key 'from' is live or not.
+
+     The marking of key 'from' has already been done or not during the marking
+     phase, and determines whether we keep entry E live during the clear-cache
+     phase.
+     If key 'from' is alive, we mark entry E as such.
+     If key 'from' is not alive:
+     - we remove the entry E from the cache, and
+     - entry E will be ggc-freed, and
+     - key 'from' will be ggc-freed.
+     - non-key 'to' will not be freed, since we conservatively marked it.  But
+       next ggc invocation, entry E will be gone and no longer cause 'to' to be
+       marked.  So 'to' may be gcc-freed the next ggc invocation.
+
+     Background: A more optimal marking strategy would be to mark the non-key
+     'to' only if key 'from' is live.  But in order to get to the transitive
+     closure of that marking, we'd need an iterate-till-fixed-point loop around
+     the traversing of all cache tables and their entries.
+     So instead we mark conservatively.  The drawback of this strategy
+     is that cache cycles are not freed.  Also, it can take several ggc
+     invocations for the effects to fully propagate.  */
+
   for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
     if (!table::is_empty (*iter) && !table::is_deleted (*iter))
       {
@@ -1053,7 +1079,7 @@ gt_cleare_cache (hash_table<H> *h)
 	if (res == 0)
 	  h->clear_slot (&*iter);
 	else if (res != -1)
-	  gt_ggc_mx (*iter);
+	  ggc_set_mark (*iter);
       }
 }
 
diff --git a/gcc/trans-mem.c b/gcc/trans-mem.c
index c809a2e..748a2b6 100644
--- a/gcc/trans-mem.c
+++ b/gcc/trans-mem.c
@@ -478,6 +478,10 @@ struct tm_wrapper_hasher : ggc_cache_ptr_hash<tree_map>
     return a->base.from == b->base.from;
   }
 
+  static void ggc_mx (tree_map *&m) {
+    gt_ggc_mx (m->to);
+  }
+
   static int
   keep_cache_entry (tree_map *&m)
   {
diff --git a/gcc/tree.c b/gcc/tree.c
index 6628a38..16afae5 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -261,6 +261,13 @@ struct tree_vec_map_cache_hasher : ggc_cache_ptr_hash<tree_vec_map>
     return a->base.from == b->base.from;
   }
 
+  static void ggc_mx (tree_vec_map *&m) {
+    /* gt_ggc_mx (vec<T, va_gc> *v) from vec.h does not do
+       ggc_test_and_set_mark, so do it here.  */
+    if (ggc_test_and_set_mark (m->to))
+      gt_ggc_mx (m->to);
+  }
+
   static int
   keep_cache_entry (tree_vec_map *&m)
   {
diff --git a/gcc/tree.h b/gcc/tree.h
index 250f99d..ae48a80 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -4626,6 +4626,8 @@ extern unsigned int tree_map_hash (const void *);
 extern unsigned int tree_decl_map_hash (const void *);
 #define tree_decl_map_marked_p tree_map_base_marked_p
 
+extern void gt_ggc_mx (tree&);
+
 struct tree_decl_map_cache_hasher : ggc_cache_ptr_hash<tree_decl_map>
 {
   static hashval_t hash (tree_decl_map *m) { return tree_decl_map_hash (m); }
@@ -4635,6 +4637,10 @@ struct tree_decl_map_cache_hasher : ggc_cache_ptr_hash<tree_decl_map>
     return tree_decl_map_eq (a, b);
   }
 
+  static void ggc_mx (tree_decl_map *&m) {
+    gt_ggc_mx (m->to);
+  }
+
   static int
   keep_cache_entry (tree_decl_map *&m)
   {
diff --git a/gcc/ubsan.c b/gcc/ubsan.c
index 19eafab..6ea5be8 100644
--- a/gcc/ubsan.c
+++ b/gcc/ubsan.c
@@ -95,6 +95,10 @@ struct tree_type_map_cache_hasher : ggc_cache_ptr_hash<tree_type_map>
     return a->type.from == b->type.from;
   }
 
+  static void ggc_mx (tree_type_map *&m) {
+    gt_ggc_mx (m->decl);
+  }
+
   static int
   keep_cache_entry (tree_type_map *&m)
   {
diff --git a/gcc/varasm.c b/gcc/varasm.c
index 3e76032..ff20941 100644
--- a/gcc/varasm.c
+++ b/gcc/varasm.c
@@ -5793,6 +5793,10 @@ 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); }
 
+  static void ggc_mx (tree_map *&m) {
+    gt_ggc_mx (m->to);
+  }
+
   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..b60c74d
--- /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 on 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

Re: [RFC] two-phase marking in gt_cleare_cache

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 2094 bytes --]

On 09/07/15 12:44, Tom de Vries wrote:
> On 07/07/15 16:00, Michael Matz wrote:
>> Hi,
>>
>> On Mon, 6 Jul 2015, Richard Biener wrote:
>>
>>>>> By doing so, we make the behaviour of gt_cleare_cache independent
>>>>> of the
>>>>> order in which the entries are visited, turning:
>>>>> - hard-to-trigger bugs which trigger for one visiting order but not
>>>>> for
>>>>>    another, into
>>>>> - more easily triggered bugs which trigger for any visiting order.
>>>>>
>>>>> Any comments?
>>>>
>>>> I think it is only half-way correct in your proposed change.  You only
>>>> fix the issue for hashes of the same kind.  To truly fix the issue
>>>> you'd
>>>> have to change generated code for gt_clear_caches () and provide
>>>> a clearing-only implementation (or pass a operation mode bool to
>>>> the core worker in hash-table.h).
>>>
>>> Hmm, and don't we rather want to first mark and _then_ clear?  Because
>>> if entry B in the hash is live and would keep A live then A _is_ kept in
>>> the end but you'll remove it from the hash, possibly no longer using a
>>> still live copy.
>>
>> I don't think such use has ever worked with the caching hash tables.
>> Even
>> the old (before c++) scheme didn't iterate, i.e. if a cache-hash entry A
>> became life from outside, but it itself kept an entry B live in the hash
>> table (with no other references to B) then this never worked (or only by
>> luck), because the slot was always cleared if !ggc_marked_p, so if B was
>> visited before A it was removed from the hash-table (and in particular
>> B's
>> gt_ggc_mx routine was never called, so whatever B needed wasn't even
>> marked).
>>
>> Given this I think the call to gt_ggc_mx is superfluous because it
>> wouldn't work relyably for multi-step dependencies anyway.  Hence a
>> situation that works with that call in place, and breaking without it is
>> actually a bug waiting to be uncovered.
>>
>
> Attached patch tries to get multi-step dependencies right, without using
> iteration-till-fixed-point.

And for the record, attached patch implements a naive iterative approach.

Thanks,
- Tom

[-- Attachment #2: 0002-Use-iterative-strategy-for-caches.patch --]
[-- Type: text/x-patch, Size: 6341 bytes --]

Use iterative strategy for caches

---
 gcc/gengtype.c   | 29 +++++++++++++++++----------
 gcc/ggc-common.c | 26 +++++++++++++++++++++++-
 gcc/ggc.h        |  2 +-
 gcc/hash-table.h | 61 ++++++++++++++++++++++++++++++++++++++++++++------------
 4 files changed, 93 insertions(+), 25 deletions(-)

diff --git a/gcc/gengtype.c b/gcc/gengtype.c
index 137e0ff..3e912e3 100644
--- a/gcc/gengtype.c
+++ b/gcc/gengtype.c
@@ -4197,7 +4197,10 @@ finish_cache_funcs (flist *flp)
   for (fli2 = flp; fli2; fli2 = fli2->next)
     if (fli2->started_p)
       {
-	oprintf (fli2->f, "}\n\n");
+	oprintf (fli2->f,
+		 "  return clear_cnt;\n"
+		 "}\n"
+		 "\n");
       }
 
   for (fli2 = flp; fli2 && base_files; fli2 = fli2->next)
@@ -4209,14 +4212,18 @@ finish_cache_funcs (flist *flp)
 	for (fnum = 0; bitmap != 0; fnum++, bitmap >>= 1)
 	  if (bitmap & 1)
 	    {
-	      oprintf (base_files[fnum], "extern void gt_clear_caches_");
+	      oprintf (base_files[fnum], "extern unsigned int gt_clear_caches_");
 	      put_mangled_filename (base_files[fnum], fli2->file);
-	      oprintf (base_files[fnum], " ();\n");
+	      oprintf (base_files[fnum], " (unsigned int);\n");
 	    }
       }
 
   for (size_t fnum = 0; base_files && fnum < num_lang_dirs; fnum++)
-    oprintf (base_files[fnum], "void\ngt_clear_caches ()\n{\n");
+    oprintf (base_files[fnum],
+	     "unsigned int\n"
+	     "gt_clear_caches (unsigned int phase)\n"
+	     "{\n"
+	     "  unsigned int clear_cnt = 0;\n");
 
   for (fli2 = flp; fli2; fli2 = fli2->next)
     if (fli2->started_p)
@@ -4229,15 +4236,17 @@ finish_cache_funcs (flist *flp)
 	for (fnum = 0; base_files && bitmap != 0; fnum++, bitmap >>= 1)
 	  if (bitmap & 1)
 	    {
-	      oprintf (base_files[fnum], "  gt_clear_caches_");
+	      oprintf (base_files[fnum], "  clear_cnt += gt_clear_caches_");
 	      put_mangled_filename (base_files[fnum], fli2->file);
-	      oprintf (base_files[fnum], " ();\n");
+	      oprintf (base_files[fnum], " (phase);\n");
 	    }
       }
 
   for (size_t fnum = 0; base_files && fnum < num_lang_dirs; fnum++)
     {
-      oprintf (base_files[fnum], "}\n");
+      oprintf (base_files[fnum],
+	       "  return clear_cnt;\n"
+	       "}\n");
     }
 }
 
@@ -4658,12 +4667,12 @@ write_roots (pair_p variables, bool emit_pch)
 	{
 	  fli->started_p = 1;
 
-	  oprintf (f, "void\ngt_clear_caches_");
+	  oprintf (f, "unsigned int\ngt_clear_caches_");
 	  put_mangled_filename (f, v->line.file);
-	  oprintf (f, " ()\n{\n");
+	  oprintf (f, " (unsigned int phase)\n{\n  unsigned int clear_cnt = 0;\n");
 	}
 
-      oprintf (f, "  gt_cleare_cache (%s);\n", v->name);
+      oprintf (f, "  clear_cnt += gt_cleare_cache (%s, phase);\n", v->name);
     }
 
   finish_cache_funcs (flp);
diff --git a/gcc/ggc-common.c b/gcc/ggc-common.c
index 5096837..110640c 100644
--- a/gcc/ggc-common.c
+++ b/gcc/ggc-common.c
@@ -100,7 +100,31 @@ ggc_mark_roots (void)
   if (ggc_protect_identifiers)
     ggc_mark_stringpool ();
 
-  gt_clear_caches ();
+  unsigned int clear_cnt, prev_clear_cnt;
+  unsigned int iteration = 0;
+
+  /* Mark.  */
+  ++iteration;
+  gt_clear_caches (1);
+
+  /* Count.  */
+  clear_cnt = gt_clear_caches (0);
+
+  do
+    {
+      prev_clear_cnt = clear_cnt;
+
+      /* Mark.  */
+      ++iteration;
+      gt_clear_caches (1);
+
+      /* Count.  */
+      clear_cnt = gt_clear_caches (0);
+    }
+  while (clear_cnt != prev_clear_cnt);
+
+  /* Clear.  */
+  gt_clear_caches (2);
 
   if (! ggc_protect_identifiers)
     ggc_purge_stringpool ();
diff --git a/gcc/ggc.h b/gcc/ggc.h
index ebc6a5d..eaf4236 100644
--- a/gcc/ggc.h
+++ b/gcc/ggc.h
@@ -54,7 +54,7 @@ extern int gt_pch_note_object (void *, void *, gt_note_pointers);
 extern void gt_pch_note_reorder (void *, void *, gt_handle_reorder);
 
 /* generated function to clear caches in gc memory.  */
-extern void gt_clear_caches ();
+extern unsigned int gt_clear_caches (unsigned int);
 
 /* Mark the object in the first parameter and anything it points to.  */
 typedef void (*gt_pointer_walker) (void *);
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 12e0c96..2408953 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -491,7 +491,8 @@ private:
   template<typename T> friend void gt_pch_nx (hash_table<T> *,
 					      gt_pointer_operator, void *);
 
-  template<typename T> friend void gt_cleare_cache (hash_table<T> *);
+  template<typename T> friend unsigned int gt_cleare_cache (hash_table<T> *,
+						    unsigned int phase);
 
   value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
   value_type *find_empty_slot_for_expand (hashval_t);
@@ -1038,23 +1039,57 @@ gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
 }
 
 template<typename H>
-inline void
-gt_cleare_cache (hash_table<H> *h)
+inline unsigned int
+gt_cleare_cache (hash_table<H> *h, unsigned int phase)
 {
+  unsigned int clear_cnt = 0;
+
   extern void gt_ggc_mx (typename H::value_type &t);
   typedef hash_table<H> table;
   if (!h)
-    return;
+    return clear_cnt;
 
-  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);
-	else if (res != -1)
-	  gt_ggc_mx (*iter);
-      }
+  typename table::iterator iter;
+  switch (phase)
+    {
+    case 0:
+      /* Phase 0: Count.  */
+      for (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)
+	      clear_cnt++;
+	  }
+      break;
+
+    case 1:
+      /* Phase 1: Mark.  */
+      for (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 == 1)
+	      gt_ggc_mx (*iter);
+	  }
+      break;
+
+    case 2:
+      /* Phase 2: Clear.  */
+      for (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);
+	  }
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return clear_cnt;
 }
 
 #endif /* TYPED_HASHTAB_H */
-- 
1.9.1

Re: [RFC] two-phase marking in gt_cleare_cache

[Michael Matz]

Hi,

On Thu, 9 Jul 2015, Tom de Vries wrote:

> > > Given this I think the call to gt_ggc_mx is superfluous because it 
> > > wouldn't work relyably for multi-step dependencies anyway.  Hence a 
> > > situation that works with that call in place, and breaking without 
> > > it is actually a bug waiting to be uncovered.
> > 
> > Attached patch tries to get multi-step dependencies right, without 
> > using iteration-till-fixed-point.
> 
> And for the record, attached patch implements a naive iterative 
> approach.

What uses do multi-step dependencies have?  As in, I think this goes into 
the wrong direction, we lived without this since years, so why should this 
situation be handled at all?  It's about cache hash tables, so they 
shouldn't contain anything that is only pointed to at by entries in those 
tables.

If anything we rather should check, that calling gt_ggc_mx on anything 
retained in the hash tables doesn't generate newly live objects.


Ciao,
Michael.

Re: [RFC] two-phase marking in gt_cleare_cache

[Tom de Vries]

On 09/07/15 14:24, Michael Matz wrote:
> Hi,
>
> On Thu, 9 Jul 2015, Tom de Vries wrote:
>
>>>> Given this I think the call to gt_ggc_mx is superfluous because it
>>>> wouldn't work relyably for multi-step dependencies anyway.  Hence a
>>>> situation that works with that call in place, and breaking without
>>>> it is actually a bug waiting to be uncovered.
>>>
>>> Attached patch tries to get multi-step dependencies right, without
>>> using iteration-till-fixed-point.
>>
>> And for the record, attached patch implements a naive iterative
>> approach.
>
> What uses do multi-step dependencies have?  As in, I think this goes into
> the wrong direction, we lived without this since years, so why should this
> situation be handled at all?  It's about cache hash tables, so they
> shouldn't contain anything that is only pointed to at by entries in those
> tables.
>
> If anything we rather should check, that calling gt_ggc_mx on anything
> retained in the hash tables doesn't generate newly live objects.
>

Hi Michael,

I'm trying to get to a defined policy for what is allowed for caches. 
Either forbidding or allowing multi-step dependencies, I don't really mind.

Until now, we didn't have a good way of allowing them. I came up with a 
runtime efficient but not exhaustive variant, which I posted here: 
https://gcc.gnu.org/ml/gcc-patches/2015-07/msg00711.html.
As contrast and for the record, I posted the exhaustive but not runtime 
efficient variant here: 
https://gcc.gnu.org/ml/gcc-patches/2015-07/msg00730.html.

I managed to write a patch series that implements the forbidding of 
multi-step dependencies. I'll post this soon.

Thanks,
- Tom

Re: [RFC] two-phase marking in gt_cleare_cache

[Tom de Vries]

On 12/07/15 17:43, Tom de Vries wrote:
> On 09/07/15 14:24, Michael Matz wrote:
>> Hi,
>>
>> On Thu, 9 Jul 2015, Tom de Vries wrote:
>>
>>>>> Given this I think the call to gt_ggc_mx is superfluous because it
>>>>> wouldn't work relyably for multi-step dependencies anyway.  Hence a
>>>>> situation that works with that call in place, and breaking without
>>>>> it is actually a bug waiting to be uncovered.
>>>>
>>>> Attached patch tries to get multi-step dependencies right, without
>>>> using iteration-till-fixed-point.
>>>
>>> And for the record, attached patch implements a naive iterative
>>> approach.
>>
>> What uses do multi-step dependencies have?  As in, I think this goes into
>> the wrong direction, we lived without this since years, so why should
>> this
>> situation be handled at all?  It's about cache hash tables, so they
>> shouldn't contain anything that is only pointed to at by entries in those
>> tables.
>>
>> If anything we rather should check, that calling gt_ggc_mx on anything
>> retained in the hash tables doesn't generate newly live objects.
>>
>
> Hi Michael,
>
> I'm trying to get to a defined policy for what is allowed for caches.
> Either forbidding or allowing multi-step dependencies, I don't really mind.
>
> Until now, we didn't have a good way of allowing them. I came up with a
> runtime efficient but not exhaustive variant, which I posted here:
> https://gcc.gnu.org/ml/gcc-patches/2015-07/msg00711.html.
> As contrast and for the record, I posted the exhaustive but not runtime
> efficient variant here:
> https://gcc.gnu.org/ml/gcc-patches/2015-07/msg00730.html.
>
> I managed to write a patch series that implements the forbidding of
> multi-step dependencies. I'll post this soon.
>

https://gcc.gnu.org/ml/gcc-patches/2015-07/msg00970.html

Thanks,
- Tom

Re: [RFC] two-phase marking in gt_cleare_cache

[Michael Matz]

Hi,

On Sun, 12 Jul 2015, Tom de Vries wrote:

> > I'm trying to get to a defined policy for what is allowed for caches. 
> > Either forbidding or allowing multi-step dependencies, I don't really 
> > mind.

I think forbidding is the way to go, because ...

> > I managed to write a patch series that implements the forbidding of 
> > multi-step dependencies. I'll post this soon.
> 
> https://gcc.gnu.org/ml/gcc-patches/2015-07/msg00970.html

... aha, it finds bugs!  So you actually had to changes some hashes to be 
non-caching for this to work, and it's all some decl-to-debug-something 
maps (well, of course, otherwise you wouldn't have run into the bug you're 
trying to fix in the first place).  I think this hints at actual bugs that 
needs fixing in the gomp branch:

As you analyzed in PR 66714, eventually a decl A is replaced by decl B, 
but its debug-expr is simply copied, and that one itself refers to decls 
(let's call them D*) that meanwhile are removed.

Now, as the D* decls are not in any other data structure (otherwise they 
would have been marked) the typical actions that needed to have been done 
for them (like e.g. associating debug info with them, allocating them to 
some stack or register place) i.e. anything that needed to be done for 
normal decls won't have been done.  So the debug info generator in this 
case, when it sees those D* decls can't do its work, e.g. debug info 
generated for D* won't refer to the real place containing the value, 
because also the generated code itself doesn't refer to D* anymore.

This also hints at other problems (which might not actually occur in the 
case at hand, but still): the contents of DECL_VALUE_EXPR is the "real" 
thing containing the value of a decl (i.e. a decl having a value-expr 
doesn't itself occur in the code anymore), be it a decl itself, or some 
expression (which might also refer to decls).  Now, in PR 66714 you 
analyzed that one of those D* was removed from the function, which should 
have happened only because no code referred to anymore, i.e. D* was also 
rewritten to some other D'* (if it weren't rewritten and D* was referred 
to in code, you would have created a miscompilation).  At that point also 
the DECL_VALUE_EXPRs need to be rewritten to refer to D'*, not to D* 
anymore.

Implementing multi-step maps or making the hashmaps non-caching doesn't 
solve any of the above problems, it merely forces some DECLs in the 
compiler to remain live but that actually have no meaning in their 
context.

So, I think this makes it pretty clear that those hashmaps should remain 
caching maps, and that multi-step deps in caches should be disallowed, and 
that the underlying problem should rather be fixed (and the checking code 
against multi-step-deps should be added to the compiler).


Ciao,
Michael.

Re: [RFC] two-phase marking in gt_cleare_cache

[Tom de Vries]

On 13/07/15 15:43, Michael Matz wrote:
> Hi,
>
> On Sun, 12 Jul 2015, Tom de Vries wrote:
>
>>> I'm trying to get to a defined policy for what is allowed for caches.
>>> Either forbidding or allowing multi-step dependencies, I don't really
>>> mind.
>
> I think forbidding is the way to go, because ...
>
>>> I managed to write a patch series that implements the forbidding of
>>> multi-step dependencies. I'll post this soon.
>>
>> https://gcc.gnu.org/ml/gcc-patches/2015-07/msg00970.html
>
> ... aha, it finds bugs!  So you actually had to changes some hashes to be
> non-caching for this to work, and it's all some decl-to-debug-something
> maps (well, of course, otherwise you wouldn't have run into the bug you're
> trying to fix in the first place).  I think this hints at actual bugs that
> needs fixing in the gomp branch:
>
> As you analyzed in PR 66714, eventually a decl A is replaced by decl B,
> but its debug-expr is simply copied, and that one itself refers to decls
> (let's call them D*) that meanwhile are removed.
>
> Now, as the D* decls are not in any other data structure (otherwise they
> would have been marked) the typical actions that needed to have been done
> for them (like e.g. associating debug info with them, allocating them to
> some stack or register place) i.e. anything that needed to be done for
> normal decls won't have been done.  So the debug info generator in this
> case, when it sees those D* decls can't do its work, e.g. debug info
> generated for D* won't refer to the real place containing the value,
> because also the generated code itself doesn't refer to D* anymore.
>
> This also hints at other problems (which might not actually occur in the
> case at hand, but still): the contents of DECL_VALUE_EXPR is the "real"
> thing containing the value of a decl (i.e. a decl having a value-expr
> doesn't itself occur in the code anymore), be it a decl itself, or some
> expression (which might also refer to decls).  Now, in PR 66714 you
> analyzed that one of those D* was removed from the function, which should
> have happened only because no code referred to anymore, i.e. D* was also
> rewritten to some other D'* (if it weren't rewritten and D* was referred
> to in code, you would have created a miscompilation).  At that point also
> the DECL_VALUE_EXPRs need to be rewritten to refer to D'*, not to D*
> anymore.
>

Thanks for looking into the PR. I suspected that these things were 
wrong, but I have no knowledge of this part of the compiler, so I was 
not sure.

> Implementing multi-step maps or making the hashmaps non-caching doesn't
> solve any of the above problems

I'm not saying that making those hashmaps non-caching solves any of 
these problems.

I'm saying that it decouples fixing the policy (for which I have a 
patch) from fixing the issues that allow us to use these 3 as caches 
again (for which there are no patches yet). The advantage of having a 
policy in place is that we won't regress for tables still marked as 
cache (or new tables marked as cache). So blocking committing the policy 
on those issues makes no sense IMHO.

Thanks,
- Tom

>, it merely forces some DECLs in the
> compiler to remain live but that actually have no meaning in their
> context.
>
> So, I think this makes it pretty clear that those hashmaps should remain
> caching maps, and that multi-step deps in caches should be disallowed, and
> that the underlying problem should rather be fixed (and the checking code
> against multi-step-deps should be added to the compiler).
>
>
> Ciao,
> Michael.
>

Re: [RFC] two-phase marking in gt_cleare_cache

[Michael Matz]

Hi,

On Mon, 13 Jul 2015, Tom de Vries wrote:

> > Implementing multi-step maps or making the hashmaps non-caching 
> > doesn't solve any of the above problems
> 
> I'm not saying that making those hashmaps non-caching solves any of 
> these problems.

Ah, I didn't mean to imply this, I meant to imply that enforcing policy as 
you do is a good thing because it finds bugs, and that the policy to be 
enforced should be forbidding multi-step deps :)

> I'm saying that it decouples fixing the policy (for which I have a 
> patch) from fixing the issues that allow us to use these 3 as caches 
> again (for which there are no patches yet). The advantage of having a 
> policy in place is that we won't regress for tables still marked as 
> cache (or new tables marked as cache). So blocking committing the policy 
> on those issues makes no sense IMHO.

That's right, I didn't argue for that either.  But there should then be at 
least a PR with a patch that disables the work-arounds for policy breakers 
(the three decl-debug hash-maps), that if applied breaks bootstrap, so 
that the fact that there's still a real bug somewhere doesn't get lost.


Ciao,
Michael.

Re: [RFC] two-phase marking in gt_cleare_cache

[Tom de Vries]

On 13/07/15 16:21, Michael Matz wrote:
> Hi,
>
> On Mon, 13 Jul 2015, Tom de Vries wrote:
>
>>> Implementing multi-step maps or making the hashmaps non-caching
>>> doesn't solve any of the above problems
>>
>> I'm not saying that making those hashmaps non-caching solves any of
>> these problems.
>
> Ah, I didn't mean to imply this, I meant to imply that enforcing policy as
> you do is a good thing because it finds bugs, and that the policy to be
> enforced should be forbidding multi-step deps :)
>
>> I'm saying that it decouples fixing the policy (for which I have a
>> patch) from fixing the issues that allow us to use these 3 as caches
>> again (for which there are no patches yet). The advantage of having a
>> policy in place is that we won't regress for tables still marked as
>> cache (or new tables marked as cache). So blocking committing the policy
>> on those issues makes no sense IMHO.
>
> That's right, I didn't argue for that either.

Great,  we're in agreement then :)

> But there should then be at
> least a PR with a patch that disables the work-arounds for policy breakers
> (the three decl-debug hash-maps), that if applied breaks bootstrap, so
> that the fact that there's still a real bug somewhere doesn't get lost.
>

Yep, there should be a PR to track these issues.

And I made the down-grades for each cache a single patch, to make it 
easy to revert once we fix all the issues for one table.

Now let's see if I can get approval for "Don't mark live recursively in 
gt_cleare_cache".

Thanks,
- Tom

[patch] PR66714 -- Re: Re: [RFC] two-phase marking in gt_cleare_cache

[Cesar Philippidis]

[-- Attachment #1: Type: text/plain, Size: 1434 bytes --]

On 07/13/2015 06:43 AM, Michael Matz wrote:

> This also hints at other problems (which might not actually occur in the 
> case at hand, but still): the contents of DECL_VALUE_EXPR is the "real" 
> thing containing the value of a decl (i.e. a decl having a value-expr 
> doesn't itself occur in the code anymore), be it a decl itself, or some 
> expression (which might also refer to decls).  Now, in PR 66714 you 
> analyzed that one of those D* was removed from the function, which should 
> have happened only because no code referred to anymore, i.e. D* was also 
> rewritten to some other D'* (if it weren't rewritten and D* was referred 
> to in code, you would have created a miscompilation).  At that point also 
> the DECL_VALUE_EXPRs need to be rewritten to refer to D'*, not to D* 
> anymore.

The attached patch does just that; it teaches
replace_block_vars_by_duplicates to replace the decls inside the
value-exprs with a duplicate too. It's kind of messy though. At the
moment I'm only considering VAR_DECL, PARM_DECL, RESULT_DECL, ADDR_EXPR,
ARRAY_REF, COMPONENT_REF, CONVERT_EXPR, NOP_EXPR, INDIRECT_REF and
MEM_REFs. I suspect that I may be missing some, but these are the only
ones that were triggered gcc_unreachable during testing.

As Tom mentioned in PR66714, this bug is present on trunk, specifically
in code using omp targets. Is this patch OK for trunk? I bootstrapped
and tested on x86_64-linux-gnu.

Cesar

[-- Attachment #2: pr66714.diff --]
[-- Type: text/x-patch, Size: 4079 bytes --]

2015-07-22  Cesar Philippidis  <cesar@codesourcery.com>
	    Tom de Vries  <vries@codesourcery.com>

	gcc/
	* tree-cfg.c (replace_by_duplicate_decl_value_expr): New function.
	(replace_block_vars_by_duplicates): Ensure that value expr decls
	have been copied usign replace_by_duplicate_decl_value_expr.

	libgomp/
	* testsuite/libgomp.c/pr66714.c: New file.
	

diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index fde7fbc..15cb122 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -6439,6 +6439,99 @@ replace_by_duplicate_decl (tree *tp, hash_map<tree, tree> *vars_map,
   *tp = new_t;
 }
 
+/* Replaces the value expression *TP with a duplicate (belonging to function
+   TO_CONTEXT).  The duplicates are recorded in VARS_MAP.  */
+
+static void
+replace_by_duplicate_decl_value_expr (tree *tp,
+				      hash_map<tree, tree> *vars_map,
+				      tree to_context)
+{
+  tree x = *tp;
+
+  switch (TREE_CODE (*tp))
+    {
+    case VAR_DECL:
+    case PARM_DECL:
+    case RESULT_DECL:
+      replace_by_duplicate_decl (tp, vars_map, to_context);
+      break;
+    case ADDR_EXPR:
+      {
+	tree expr = TREE_OPERAND (x, 0);
+
+	replace_by_duplicate_decl_value_expr (&expr, vars_map, to_context);
+	*tp = build1 (ADDR_EXPR, TREE_TYPE (x), expr);
+      }
+      break;
+    case ARRAY_REF:
+      {
+	tree array = TREE_OPERAND (x, 0);
+	tree index = TREE_OPERAND (x, 1);
+	tree arg2 = TREE_OPERAND (x, 2);
+	tree arg3 = TREE_OPERAND (x, 3);
+
+	replace_by_duplicate_decl (&array, vars_map, to_context);
+	replace_by_duplicate_decl (&index, vars_map, to_context);
+
+	*tp = build4 (ARRAY_REF, TREE_TYPE (x), array, index,
+		      arg2, arg3);
+      }
+      break;
+    case COMPONENT_REF:
+      {
+	tree component = TREE_OPERAND (x, 0);
+	tree field = TREE_OPERAND (x, 1);
+	tree ref;
+
+	/* Components may be MEM_REFs.  */
+	replace_by_duplicate_decl_value_expr (&component, vars_map,
+					      to_context);
+	ref = build3 (COMPONENT_REF, TREE_TYPE (field), component,
+		      field, NULL);
+
+	if (TREE_THIS_VOLATILE (x))
+	  TREE_THIS_VOLATILE (ref) |= 1;
+	if (TREE_READONLY (x))
+	  TREE_READONLY (ref) |= 1;
+
+	*tp = ref;
+      }
+      break;
+    case CONVERT_EXPR:
+    case NOP_EXPR:
+    case INDIRECT_REF:
+      {
+	tree expr = TREE_OPERAND (x, 0);
+	tree decl;
+
+	if (CONVERT_EXPR_CODE_P (TREE_CODE (expr)))
+	  decl = TREE_OPERAND (expr, 0);
+	else
+	  decl = expr;
+
+	replace_by_duplicate_decl (&decl, vars_map, to_context);
+
+	if (CONVERT_EXPR_CODE_P (TREE_CODE (expr)))
+	  expr = build1 (TREE_CODE (expr), TREE_TYPE (expr), decl);
+	else
+	  expr = decl;
+
+	*tp = build_simple_mem_ref (expr);
+      }
+      break;
+    case MEM_REF:
+      {
+	tree mem = TREE_OPERAND (x, 0);
+
+	replace_by_duplicate_decl_value_expr (&mem, vars_map, to_context);
+	*tp = build_simple_mem_ref (mem);
+      }
+      break;
+    default:
+      gcc_unreachable ();
+    }
+}
 
 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
    VARS_MAP maps old ssa names and var_decls to the new ones.  */
@@ -6916,7 +7009,11 @@ replace_block_vars_by_duplicates (tree block, hash_map<tree, tree> *vars_map,
 	{
 	  if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
 	    {
-	      SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
+	      tree x = DECL_VALUE_EXPR (*tp);
+
+	      replace_by_duplicate_decl_value_expr (&x, vars_map, to_context);
+
+	      SET_DECL_VALUE_EXPR (t, x);
 	      DECL_HAS_VALUE_EXPR_P (t) = 1;
 	    }
 	  DECL_CHAIN (t) = DECL_CHAIN (*tp);
diff --git a/libgomp/testsuite/libgomp.c/pr66714.c b/libgomp/testsuite/libgomp.c/pr66714.c
new file mode 100644
index 0000000..c9af4a9
--- /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 on 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;
+}

Re: [patch] PR66714 -- Re: Re: [RFC] two-phase marking in gt_cleare_cache

[Jakub Jelinek]

On Thu, Jul 23, 2015 at 08:20:50AM -0700, Cesar Philippidis wrote:
> The attached patch does just that; it teaches
> replace_block_vars_by_duplicates to replace the decls inside the
> value-exprs with a duplicate too. It's kind of messy though. At the
> moment I'm only considering VAR_DECL, PARM_DECL, RESULT_DECL, ADDR_EXPR,
> ARRAY_REF, COMPONENT_REF, CONVERT_EXPR, NOP_EXPR, INDIRECT_REF and
> MEM_REFs. I suspect that I may be missing some, but these are the only
> ones that were triggered gcc_unreachable during testing.

Ugh, that looks ugly, why do we have all the tree walkers?
I'd unshare_expr the value expr first, you really don't want to share
it anyway, and then just walk_tree and find all the decls in there
(with *walk_subtrees on types and perhaps something else too) and for them
replace_by_duplicate_decl (tp, vars_map, to_context);

	Jakub

Re: [patch] PR66714 -- Re: Re: [RFC] two-phase marking in gt_cleare_cache

[Cesar Philippidis]

[-- Attachment #1: Type: text/plain, Size: 1025 bytes --]

On 07/23/2015 08:32 AM, Jakub Jelinek wrote:
> On Thu, Jul 23, 2015 at 08:20:50AM -0700, Cesar Philippidis wrote:
>> The attached patch does just that; it teaches
>> replace_block_vars_by_duplicates to replace the decls inside the
>> value-exprs with a duplicate too. It's kind of messy though. At the
>> moment I'm only considering VAR_DECL, PARM_DECL, RESULT_DECL, ADDR_EXPR,
>> ARRAY_REF, COMPONENT_REF, CONVERT_EXPR, NOP_EXPR, INDIRECT_REF and
>> MEM_REFs. I suspect that I may be missing some, but these are the only
>> ones that were triggered gcc_unreachable during testing.
> 
> Ugh, that looks ugly, why do we have all the tree walkers?
> I'd unshare_expr the value expr first, you really don't want to share
> it anyway, and then just walk_tree and find all the decls in there
> (with *walk_subtrees on types and perhaps something else too) and for them
> replace_by_duplicate_decl (tp, vars_map, to_context);

Something like the attached patch? Why do TREE_TYPEs need special handling?

Is it OK for trunk?

Cesar

[-- Attachment #2: pr66714-2.diff --]
[-- Type: text/x-patch, Size: 2882 bytes --]

2015-07-23  Cesar Philippidis  <cesar@codesourcery.com>

	gcc/
	* tree-cfg.c (struct replace_decls_d): New struct.
	(replace_block_vars_by_duplicates_1): New function.
	(replace_block_vars_by_duplicates): Use it to replace the decls
	in the value exprs by duplicates.

	libgomp/
	* testsuite/libgomp.c/pr66714.c: New test.


diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index fde7fbc..900274a 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -70,6 +70,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "omp-low.h"
 #include "tree-cfgcleanup.h"
 #include "wide-int-print.h"
+#include "gimplify.h"
 
 /* This file contains functions for building the Control Flow Graph (CFG)
    for a function tree.  */
@@ -108,6 +109,13 @@ struct cfg_stats_d
 
 static struct cfg_stats_d cfg_stats;
 
+/* Data to pass to replace_block_vars_by_duplicates_1.  */
+struct replace_decls_d
+{
+  hash_map<tree, tree> *vars_map;
+  tree to_context;
+};
+
 /* Hash table to store last discriminator assigned for each locus.  */
 struct locus_discrim_map
 {
@@ -6897,6 +6905,29 @@ new_label_mapper (tree decl, void *data)
   return m->to;
 }
 
+/* Tree walker to replace the decls used inside value expressions by
+   duplicates.  */
+
+static tree
+replace_block_vars_by_duplicates_1 (tree *tp, int *walk_subtrees, void *data)
+{
+  struct replace_decls_d *rd = (struct replace_decls_d *)data;
+
+  switch (TREE_CODE (*tp))
+    {
+    case VAR_DECL:
+    case PARM_DECL:
+    case RESULT_DECL:
+      replace_by_duplicate_decl (tp, rd->vars_map, rd->to_context);
+      *walk_subtrees = 0;
+      break;
+    default:
+      break;
+    }
+
+  return NULL;
+}
+
 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
    subblocks.  */
 
@@ -6916,7 +6947,11 @@ replace_block_vars_by_duplicates (tree block, hash_map<tree, tree> *vars_map,
 	{
 	  if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
 	    {
-	      SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
+	      tree x = DECL_VALUE_EXPR (*tp);
+	      struct replace_decls_d rd = { vars_map, to_context };
+	      unshare_expr (x);
+	      walk_tree (&x, replace_block_vars_by_duplicates_1, &rd, NULL);
+	      SET_DECL_VALUE_EXPR (t, x);
 	      DECL_HAS_VALUE_EXPR_P (t) = 1;
 	    }
 	  DECL_CHAIN (t) = DECL_CHAIN (*tp);
diff --git a/libgomp/testsuite/libgomp.c/pr66714.c b/libgomp/testsuite/libgomp.c/pr66714.c
new file mode 100644
index 0000000..c9af4a9
--- /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 on 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;
+}

Re: [patch] PR66714 -- Re: Re: [RFC] two-phase marking in gt_cleare_cache

[Jakub Jelinek]

On Thu, Jul 23, 2015 at 03:01:25PM -0700, Cesar Philippidis wrote:
> On 07/23/2015 08:32 AM, Jakub Jelinek wrote:
> > On Thu, Jul 23, 2015 at 08:20:50AM -0700, Cesar Philippidis wrote:
> >> The attached patch does just that; it teaches
> >> replace_block_vars_by_duplicates to replace the decls inside the
> >> value-exprs with a duplicate too. It's kind of messy though. At the
> >> moment I'm only considering VAR_DECL, PARM_DECL, RESULT_DECL, ADDR_EXPR,
> >> ARRAY_REF, COMPONENT_REF, CONVERT_EXPR, NOP_EXPR, INDIRECT_REF and
> >> MEM_REFs. I suspect that I may be missing some, but these are the only
> >> ones that were triggered gcc_unreachable during testing.
> > 
> > Ugh, that looks ugly, why do we have all the tree walkers?
> > I'd unshare_expr the value expr first, you really don't want to share
> > it anyway, and then just walk_tree and find all the decls in there
> > (with *walk_subtrees on types and perhaps something else too) and for them
> > replace_by_duplicate_decl (tp, vars_map, to_context);
> 
> Something like the attached patch? Why do TREE_TYPEs need special handling?

They can have decls in various places like TYPE_SIZE_UNIT, TYPE_SIZE, the
bounds of TYPE_DOMAIN etc. and I believe you generally don't want to replace
those.  Plus you risk infinite recursion then (unless walk_tree_without_duplicates).
Most walk_tree callbacks just do something like
  if (IS_TYPE_OR_DECL_P (*tp))
    *walk_subtrees = 0;

	Jakub

Re: [patch] PR66714 -- Re: Re: [RFC] two-phase marking in gt_cleare_cache

[Cesar Philippidis]

[-- Attachment #1: Type: text/plain, Size: 1588 bytes --]

On 07/23/2015 03:11 PM, Jakub Jelinek wrote:
> On Thu, Jul 23, 2015 at 03:01:25PM -0700, Cesar Philippidis wrote:
>> On 07/23/2015 08:32 AM, Jakub Jelinek wrote:
>>> On Thu, Jul 23, 2015 at 08:20:50AM -0700, Cesar Philippidis wrote:
>>>> The attached patch does just that; it teaches
>>>> replace_block_vars_by_duplicates to replace the decls inside the
>>>> value-exprs with a duplicate too. It's kind of messy though. At the
>>>> moment I'm only considering VAR_DECL, PARM_DECL, RESULT_DECL, ADDR_EXPR,
>>>> ARRAY_REF, COMPONENT_REF, CONVERT_EXPR, NOP_EXPR, INDIRECT_REF and
>>>> MEM_REFs. I suspect that I may be missing some, but these are the only
>>>> ones that were triggered gcc_unreachable during testing.
>>>
>>> Ugh, that looks ugly, why do we have all the tree walkers?
>>> I'd unshare_expr the value expr first, you really don't want to share
>>> it anyway, and then just walk_tree and find all the decls in there
>>> (with *walk_subtrees on types and perhaps something else too) and for them
>>> replace_by_duplicate_decl (tp, vars_map, to_context);
>>
>> Something like the attached patch? Why do TREE_TYPEs need special handling?
> 
> They can have decls in various places like TYPE_SIZE_UNIT, TYPE_SIZE, the
> bounds of TYPE_DOMAIN etc. and I believe you generally don't want to replace
> those.  Plus you risk infinite recursion then (unless walk_tree_without_duplicates).
> Most walk_tree callbacks just do something like
>   if (IS_TYPE_OR_DECL_P (*tp))
>     *walk_subtrees = 0;

This patch the check for IS_TYPE_OF_DECL_P in this patch. Is this ok for
trunk?

Cesar

[-- Attachment #2: pr66714.diff --]
[-- Type: text/x-patch, Size: 2919 bytes --]

2015-07-24  Cesar Philippidis  <cesar@codesourcery.com>

	gcc/
	* tree-cfg.c (struct replace_decls_d): New struct.
	(replace_block_vars_by_duplicates_1): New function.
	(replace_block_vars_by_duplicates): Use it to replace the decls
	in the value exprs by duplicates.

	libgomp/
	* testsuite/libgomp.c/pr66714.c: New test.
	

diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index fde7fbc..cb9fe6d 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -70,6 +70,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "omp-low.h"
 #include "tree-cfgcleanup.h"
 #include "wide-int-print.h"
+#include "gimplify.h"
 
 /* This file contains functions for building the Control Flow Graph (CFG)
    for a function tree.  */
@@ -108,6 +109,13 @@ struct cfg_stats_d
 
 static struct cfg_stats_d cfg_stats;
 
+/* Data to pass to replace_block_vars_by_duplicates_1.  */
+struct replace_decls_d
+{
+  hash_map<tree, tree> *vars_map;
+  tree to_context;
+};
+
 /* Hash table to store last discriminator assigned for each locus.  */
 struct locus_discrim_map
 {
@@ -6897,6 +6905,31 @@ new_label_mapper (tree decl, void *data)
   return m->to;
 }
 
+/* Tree walker to replace the decls used inside value expressions by
+   duplicates.  */
+
+static tree
+replace_block_vars_by_duplicates_1 (tree *tp, int *walk_subtrees, void *data)
+{
+  struct replace_decls_d *rd = (struct replace_decls_d *)data;
+
+  switch (TREE_CODE (*tp))
+    {
+    case VAR_DECL:
+    case PARM_DECL:
+    case RESULT_DECL:
+      replace_by_duplicate_decl (tp, rd->vars_map, rd->to_context);
+      break;
+    default:
+      break;
+    }
+
+  if (IS_TYPE_OR_DECL_P (*tp))
+    *walk_subtrees = false;
+
+  return NULL;
+}
+
 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
    subblocks.  */
 
@@ -6916,7 +6949,11 @@ replace_block_vars_by_duplicates (tree block, hash_map<tree, tree> *vars_map,
 	{
 	  if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
 	    {
-	      SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
+	      tree x = DECL_VALUE_EXPR (*tp);
+	      struct replace_decls_d rd = { vars_map, to_context };
+	      unshare_expr (x);
+	      walk_tree (&x, replace_block_vars_by_duplicates_1, &rd, NULL);
+	      SET_DECL_VALUE_EXPR (t, x);
 	      DECL_HAS_VALUE_EXPR_P (t) = 1;
 	    }
 	  DECL_CHAIN (t) = DECL_CHAIN (*tp);
diff --git a/libgomp/testsuite/libgomp.c/pr66714.c b/libgomp/testsuite/libgomp.c/pr66714.c
new file mode 100644
index 0000000..c9af4a9
--- /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 on 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;
+}

Re: [patch] PR66714 -- Re: Re: [RFC] two-phase marking in gt_cleare_cache

[Jakub Jelinek]

On Fri, Jul 24, 2015 at 07:21:07AM -0700, Cesar Philippidis wrote:
> This patch the check for IS_TYPE_OF_DECL_P in this patch. Is this ok for
> trunk?

> 2015-07-24  Cesar Philippidis  <cesar@codesourcery.com>
> 
> 	gcc/
> 	* tree-cfg.c (struct replace_decls_d): New struct.
> 	(replace_block_vars_by_duplicates_1): New function.
> 	(replace_block_vars_by_duplicates): Use it to replace the decls
> 	in the value exprs by duplicates.
> 
> 	libgomp/
> 	* testsuite/libgomp.c/pr66714.c: New test.

Ok, thanks.

	Jakub