It would mean "take our losses" and not be perfect. Some
duplication
would exist that we don't detect. I am just suggesting that to get at
least some results (that is if the dwarf comparator wouldn't be too slow
also, then we could plug in a dwarf writer and see how far we get).
I see. I am moderately skeptical about this. All the real world cases
where we need the big wins include some complex cycles. Of course,
anything is worth trying if it doesn't take too much time to try it.
We can estimate moderately well without a writer, just looking at --stats
output or perhaps doing some slightly more sophisticated calculations.
That takes advantage of the fact that we know we can ignore the order
of
the children of a top-level CU, but I think we cannot do that easily for
any deeper nested DIE children.
I think the problem cases of <pointer_type type=.../> et al normally,
perhaps always, appear at top level. But note that this is not actually
ignoring even that the ordering for purposes of exactitude--it's only
ignoring it for the purpose of where in each cycle to consider the "start".
And how would we decide the correct canonical order? If we look at
something like this, then it looks like we should pick pointer_types
first and then variables.
My idea was that any canonicalization would do.
Its only purpose is to be consistent wrt following cycles.
But, like I said, I haven't thought the idea through.
<compile_unit>
<structure_type ref="ref2" name="list">
<member name="next" type="#ref1"/>
</structure_type>
<pointer_type ref="ref1" type="#ref2"/>
<variable name="var" type="#ref3"/>
<pointer_type ref="ref3" type="#ref2"/>
</compile_unit>
<compile_unit>
<structure_type ref="ref2" name="list">
<member name="next" type="#ref1"/>
</structure_type>
<pointer_type ref="ref1" type="#ref2"/>
<variable name="var" type="#ref1"/>
</compile_unit>
This seems to be a good counterexample to my idea. What I suggested
addresses choosing a canonical starting point for a reference cycle so
that we walk two identical cycles with the same steps. But it doesn't
help with two *equivalent* cycles as in this case. I was only thinking of:
<compile_unit>
<pointer_type ref="ref1" type="#ref2"/>
<structure_type ref="ref2" name="list">
<member name="next" type="#ref1"/>
</structure_type>
</compile_unit>
vs
<compile_unit>
<structure_type ref="ref2" name="list">
<member name="next" type="#ref1"/>
</structure_type>
<pointer_type ref="ref1" type="#ref2"/>
</compile_unit>
Today we have the problem you cited of walking the first cycle as
"ref1, ref2, ref1" vs walking the second as "ref2, ref1, ref2".
I thought of a way to canonicalize that ordering.
Thanks,
Roland