Re: dwarf_output overview

[Mark Wielaard <mjw at redhat dot com>]

On Tue, 2010-07-20 at 05:22 -0700, Roland McGrath wrote:
> If there are no reference attributes to consider, then it proceeds from the
> bottom up in the same straightforward way.  That is, the entire map of
> attributes (considered as a sequence of <int name, attr_value> pairs in a
> canonical name-keyed order) can be hashed together to get a hash value for
> the attributes container.  Then a leaf node can combine the tag into the
> that hash value to get a hash value for the whole DIE.  Then, a sequence of
> sibling leaf nodes' hash values are combined to form a hash value for the
> whole children container.  Then that hash value is combined with the tag
> and the attribute map hash value to form a hash value for the whole DIE.
> Then on up.

Wouldn't you also like to pass parts of the parent DIEs down? Since we
consider context of a DIE relevant for deciding whether they are really
similar. You could add a "context hash" to each DIE based on the simple
(non-reference) attributes of the parent they are embedded in. That way
two DIEs in different context would normally not get the same hash, so
you don't need to compare them plus checking their contexts are the
same.

> If that's all there were to do, it would be easy.  
> Of course, there are circular references.
> 
> So say we have:
> 
> 	<structure_type id="t1" name="list">
> 	  <member name="next" type="#p1"/>
> 	</structure_type>
> 	<pointer_type id="p1" type="#t1"/>
> 
> Now, the structure_type's own attribute map is simple, so that hashes up
> nicely.  But, the member's attribute map includes a circular reference.
> So, what we do is still hash up the whole attribute map, but use zero as
> the hash value for the reference value.  Now <member/> as a whole has a
> hash value that contributes to the children vector hash value, and that
> contributes to the structure_type's overall hash value.

Since you detect the cycle, could you use the smallest cycle size
instead of zero? Meaning, after X steps following this ref (in some
specific order), you find yourself again. That assumes that DIEs you
want to detect equal have the same circular reference structure.

Cheers,

Mark