Re: more dwarf_output stumbling

[Roland McGrath <roland at redhat dot com>]

> The local hash for dies is now no longer (re)calculated in the
> dwarf_output::debug_info_entry hierarchy, but stored in the
> die_info. This is calculated when the pending_entry is finalized.
> This also puts all calculations in one place.

That makes sense to me.

> This is slightly too late (or too early depending on how you look at
> it). Although at that time all children of the die have already been
> finalized, not all (circular) references have. But we are putting the
> candidate into the collector anyway.

It's neither too late nor too early, it's just right.  The whole subtree is
being finalized, and that's what matters.  Circularities only affect the
order in which you can do the final "placement" and subsequent reification
of references to their proper iterators into finalized children vectors.

> At first I thought that I just needed to get rid of the attributes_type
> cache, since that is where the reference chasing ends up. That would get
> rid of some complexity, but doesn't actually solve the actual algorithmic
> problem. Then the reference chasing ends up in the hash calculation of
> the debug_info_entry itself. So I abandoned that idea for now.

Right, this change should not be material to the essential algorithm.  It
only affects the complexity of the code (in which direction, it's hard to
tell ;-), and the memory vs CPU time (in hash collision comparisons)
tradeoff that I mentioned earlier.

> Instead what we need is to make sure that the local hash is calculated
> for every entry die before we try to put the attributes_type (or
> debug_info_entry) into the collector, since the full hash is based on the
> reference attributes, which can point to any die, and so need their local
> hash set.

That sounds right.

> So I am now looking at only calculating the local hash when we currently
> finalize, but don't put the items directly in the cache, but only after
> we scanned over the whole CU. That way when we do put the item in the
> cache, we can calculate the full hash because we can be sure that all
> dies that the reference attributes (recursively) points at have their
> local hash set.

I can't tell whether that sounds like exactly what I always thought the
plan of the new algorithm was, or sounds like you're still not changing the
old way of doing things enough.

"When we currently finalize" is based on all the dismal hairy bookkeeping
that we ought to be getting rid of.  In initial cut of the new plan,
nothing actually gets finalized until the whole CU is being finalized.
For the basic algorithm, the only aspect of the bookkeeping hair that we
need to preserve is noting the places with circular references so that we
can back-patch those after final placement.  For a really straightforward
first cut, you could record all forward references of any kind that way,
so that you just do a single back-patching pass after the whole CU is
finalized in tree order and that's the only means of reifying references.
(This version of back-patching is nearly as simple as dwarf_edit's
dwarf_ref_maker logic.)

For the slight refinement of the basic algorithm, we do the simple level
of bookkeeping that notices when a subtree has no references at all, or
has only references to things already found finalized in the collector.
That's just enough to permit early finalization of the simple leaves,
percolating up to early finalization of the subtrees containing those,
and thus percolating up to early finalization of all subtrees that contain
only backward references.  When early finalization already finalized a
previous duplicate, then this also covers forward references to previously
finalized duplicates.


Thanks,
Roland