On 12/16/20 5:29 PM, Richard Sandiford wrote:
> Jeff Law <l...@redhat.com> writes:
>> On 11/13/20 1:15 AM, Richard Sandiford via Gcc-patches wrote:
>>> We already have two splay tree implementations: the old C one in
>>> libiberty and a templated reimplementation of it in typed-splay-tree.h.
>>> However, they have some drawbacks:
>>>
>>> - They hard-code the assumption that nodes should have both a key and
>>> a value, which isn't always true.
>>>
>>> - They use the two-phase method of lookup, and so nodes need to store
>>> a temporary back pointer. We can avoid that overhead by using the
>>> top-down method (as e.g. the bitmap tree code already does).
>>>
>>> - The tree node has to own the key and the value. For some use cases
>>> it's more convenient to embed the tree links in the value instead.
>>>
>>> Also, a later patch wants to use splay trees to represent an
>>> adaptive total order: the splay tree itself records whether node N1
>>> is less than node N2, and (in the worst case) comparing nodes is
>>> a splay operation.
>>>
>>> This patch therefore adds an alternative implementation. The main
>>> features are:
>>>
>>> - Nodes can optionally point back to their parents.
>>>
>>> - An Accessors class abstracts accessing child nodes and (where
>>> applicable) parent nodes, so that the information can be embedded
>>> in larger data structures.
>>>
>>> - There is no fixed comparison function at the class level. Instead,
>>> individual functions that do comparisons take a comparison function
>>> argument.
>>>
>>> - There are two styles of comparison function, optimised for different
>>> use cases. (See the comments in the patch for details.)
>>>
>>> - It's possible to do some operations directly on a given node,
>>> without knowing whether it's the root. This includes the comparison
>>> use case described above.
>>>
>>> This of course has its own set of drawbacks. It's really providing
>>> splay utility functions rather than a true ADT, and so is more low-level
>>> than the existing routines. It's mostly geared for cases in which the
>>> client code wants to participate in the splay operations to some extent.
>>>
>>> gcc/
>>> * Makefile.in (OBJS): Add splay-tree-utils.o.
>>> * system.h: Include <array> when INCLUDE_ARRAY is defined.
>>> * selftest.h (splay_tree_cc_tests): Declare.
>>> * selftest-run-tests.c (selftest::run_tests): Run splay_tree_cc_tests.
>>> * splay-tree-utils.h: New file.
>>> * splay-tree-utils.tcc: Likewise.
>>> * splay-tree-utils.cc: Likewise.
>> I must admit, I'm not a fan of adding another splay tree. Though I
>> suspect the one in libiberty will be there forever since there could
>> well be clients outside our source base.
>>
>> The typed_splay_tree implementation however is internal to GCC and only
>> has a couple users (the JIT and fixit hints). Is there any chance we
>> could convert those two users to the new one? Your cover hints that's
>> not the case, but I'm going to explicitly ask :-)
> Yeah, I agree it's not great to have three versions. I had a look at
> converting the uses of typed_splay_tree, and all of them seem to be a
> natural fit for the new scheme. In particular, although typed_splay_tree
> maps keys to values, in practice the keys are already part of the values.
>
> However, I think a natural conversion would need a couple of new helpers
> for “get or insert” type operations. Would it be OK to wait until GCC 12
> stage 1 for that?
Yea, at this point deferring the conversion to gcc-12 seems to make the
most sense.
jeff
