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
