Re: comparing die trees/graphs

[Roland McGrath <roland at redhat dot com>]

> Yes, they are semantically equal. I was just pointing out that this is
> an extra syntactical equivalence recognition step. These do add up. The
> concern is more with the added complexity. It might not be that bad in
> practice though.

This is just the first example of new complexity.  My ad hoc algorithm
covered that much (not clear how efficiently), but there was more to come
along in practice.  And everything was too slow, though it's still not
entirely clear how much of that was algorithmic.  So, the task is to handle
all possible complexity as efficiently as we can.

> > That's not how I approached it in dwarfcmp.  But that is similar to the
> > approach in dwarf_output, where "comparison" is only part of the issue.
> 
> OK, so some of the equivalence detection can be done when we read in the
> original DIEs and others when we write out the DIEs again.

I don't really follow this comment at all.  

The mandate for dwarfcmp is to handle any valid physical formulation of
each input and say correctly whether they are semantically equivalent,
and there is no writing out involved at all there.

The existing design for dwarf_output has two phases: copy construction,
which is what drives all the reading and creation of internal memory
representations of CUs; and output, where format writing is done.
All of the duplicate detection is part of the first phase.

We haven't really talked about that whole design yet to establish a
shared vocabulary, so picking apart your remark this way is probably
premature.  But, I really don't know what you meant.

> We talked about this a little on irc. Just for the list. The example was
> just to highlight that the physical tree (where imported_unit entries
> are not expanded) is simpler to compare because there are equal nodes
> that don't need any walking. (dwarflint could/can check that
> imported_unit subtrees are used only in equivalent context.)

Yes.  Petr, this should go on the to-do list for dwarflint.  (Where is
that list kept?)  Multiple DW_TAG_imported_unit DIEs referring to a
given CU (partial_unit or compile_unit DIE) must appear in equivalent
contexts.  That is, be owned by a DIE of the same tag and equal-enough
attributes, in an equivalent context (iterate).  Eventually we'll
probably have some user knobs and common code for the equal-enough
predicate's meaning.


Thanks,
Roland