Re: [RFC] two-phase marking in gt_cleare_cache

[Tom de Vries <Tom_deVries at mentor dot com>]

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