In the C++ interface, we represent a reference-class attribute with a debug_info_entry::iterator. This works nicely for purposes of navigation. You can use it like a pointer to the debug_info_entry.

But that doesn't help for the "semantic equality" check that we want in attribute::operator== as used by e.g. dwarfcmp. Pointer equality is not the right test when comparing references in two parallel DIE trees.

So, what does "reference equality" mean for a comparison between two trees from two different DWARF files? This is not only part of making dwarfcmp do something useful, but also essential at the crux of the identification of duplicate trees that is what the compression plan is all about.

At first blush, a simple answer is that two references are identical if the subtrees they point to are identical (by deep comparison). But for important semantic purposes, that definition is too generous.

Consider a trivial C++ example:

main.cc: namespace A { #include "foo.cc" }; namespace B { #include "foo.cc" }; A::foo var; foo.cc: struct foo { int x, y; };

This yields the DIE tree (omitting lots of the irrelevant detail):

#a10: compile_unit{name="main.cc", ...} #a20: namespace{name="A", decl_file=["main.cc"], decl_line=1} #a30: structure_type{name="foo", decl_file=["foo.cc"], decl_line=1} ... #a40: namespace{name="B", decl_file=["main.cc"], decl_line=4} #a50: structure_type{name="foo", decl_file=["foo.cc"], decl_line=1} ... #a60: variable{name="var", location=..., type=#a50}

Note the #a30 and #a50 subtrees are identical. Now compare a second file:

main.cc: namespace A { #include "foo.cc" }; namespace B { #include "foo.cc" }; B::foo var; // <--- B:: vs A:: above (foo.cc same as above)

This yields the corresponding DIE tree:

#b10: compile_unit{name="main.cc", ...} #b20: namespace{name="A", decl_file=["main.cc"], decl_line=1} #b30: structure_type{name="foo", decl_file=["foo.cc"], decl_line=1} ... #b40: namespace{name="B", decl_file=["main.cc"], decl_line=4} #b50: structure_type{name="foo", decl_file=["foo.cc"], decl_line=1} ... #b60: variable{name="var", location=..., type=#b30}

(The only difference from s/a/b/ is #b60:type.) Since #a30, #a50, #b30, and #b50 are all identical, #b60's type=#b30 matches #a60's type=#a50 and we would call #a10 and #b10 identical.

But we know this is wrong. In #a60 type=#a50 is required and type=#a30 would not do, not because the subtrees pointed to differ, but because their contexts differ. Context matters: here it is the difference between resolving to A::foo and resolving to B::foo.

We have to get this right for dwarfcmp to be right at its job of semantic equality comparison. Moreover, we need to get it right in deciding where we can really consolidate redundant DIE trees to effect compression via DW_AT_imported_unit pointers. Whenever there are refs pointing to both identical copies of a duplicated DIE, we have to be sure that those two refs should be equal before we can unify those two DIEs into one in the output.

So, what should count as "equal context" for two DIEs? What comes to mind is the sequence of parent DIEs back to (but not including) the compile_unit. One thought was just to compare tags and names (or lack thereof). Another is to compare tags and all attributes. Or maybe somewhere in between. Are there attributes that are going to give us mismatches where we would like to consolidate? (DW_AT_sibling of course does not count.)

This presupposes that one thing that does not matter is the ordering of a DIE among its parent's other children. DIE children certainly are ordered in DWARF, so it could very well matter in the abstract. I have the impression there are some arcane cases with C++ namespace and using declarations where that ordering is relevant to decoding the context. But I don't have any clear sense of that or any other case where this kind of ordering matters.

That is, of course order matters all over, e.g. "void foo(int x, int y)" vs "void foo(int y, int x)" produces DIE trees that only differ (and importantly so) in the order of the two DW_TAG_formal_parameter children. But I don't see how you could have two {formal_parameter "x" child of subprogram "foo" child of CU} (say) with all matching attrs, to each of which different things had a ref attr, yet there could be both of them in the same (logical) CU such that a tree walk from the base of the CU to find the one the ref points to would be ambiguous. But I fear for some hairy corners about that.

Clearly we would hamstring useful compression enormously if we count "equal context" only when the containing DIE was completely identical. That is probably in practice far worse than the most simple and naively conservative plan: considering two DIEs identical only when they are both immediate children of a compile_unit. That simple plan is definitely fine for C, and might even be OK for C++ though perhaps only in all but its most obscure corners.

My inclination is to start out with the plan to ignore ordering for the "context equality" part of reference equality. Conversely, be conservative in excluding none of the rest of context: compare all attributes. In dwarfcmp, this means the references will pass equality comparison, but then the trees as a whole still won't pass when there is a child order difference. For compression, it might mean foregoing some cases (and leaving duplicate DIEs) where conflation of the two references so you can't distinguish which of the two original DIEs it means might be entirely harmless. Consider:

a.c: void foo (void) { #include "b.c" #include "b.c" } b.c: { typedef int itype; itype x; bar (&x); }

This will generate two almost-identical lexical_block subtrees that differ only in their PC attributes. This means the child DIEs for "itype", "x", etc. have to be duplicated, just so that a reference to the first lexical_block's "itype" will be distinct from a reference to the second lexical_block's "itype". It almost certainly never matters to distinguish them for this case.

At a guess, cases like that don't seem real likely to appear in numbers. In the long run, we may want to address this with an extension form for two-pointer refs. That would allow the most aggressive DIE deduplication possible, consolidating all identical subtrees regardless of context. Then each ref itself gives not only the pointer to that DIE, but the pointer to the imported_unit DIE that is outermost among those in the logical walk you would do from the CU to arrive at the referenced DIE. That second ref disambiguates the direct DIE ref, so the two-pointer ref identifies which copy it would point to if the compressed form were splayed back out to the logical DIE view that inserts copies where DW_TAG_imported_unit appears.

As an implementation matter, determining this "context" to compare will entail a lot of tree walking. This requires some caching, something like a reference tracker class that parameterizes the dwarf classes. This may add some complication to the definition of those whole class trees.

I'd appreciate feedback on all this thinking. (I have thought a bit more than that about the implementation, too, though far from worked it all out.)

Thanks, Roland