Re: [08/23] Add an alternative splay tree implementation

[Richard Biener via Gcc-patches]

On Mon, Jan 4, 2021 at 4:43 PM Richard Sandiford via Gcc-patches
 wrote:
>
> Andreas Schwab  writes:
> > On Jan 04 2021, Richard Sandiford wrote:
> >
> >> Andreas Schwab  writes:
> >>> That doesn't build with gcc 4.8:
> >>
> >> Which subversion are you using?
> >
> > This is 4.8.1.
>
> Hmm, OK.  I guess that raises the question whether “supporting GCC 4.8”
> means supporting every patchlevel, or just the latest.

We document

@item ISO C++11 compiler
Necessary to bootstrap GCC.
...

To build all languages in a cross-compiler or other configuration where
3-stage bootstrap is not performed, you need to start with an existing
GCC binary (version 4.8 or later) because source code for language
frontends other than C might use GCC extensions.

Note that to bootstrap GCC with versions of GCC earlier than 4.8, you
may need to use @option{--disable-stage1-checking}, though
bootstrapping the compiler with such earlier compilers is strongly
discouraged.

while the second paragraph suggests GCC 4.8 or later works
(which IMHO includes GCC 4.8.1), the general requirement
lists a C++11 compiler which appearantly GCC 4.8.1 isn't ;)

So for simplicity I'd suggest to be more precise and say
4.8.2 or later (if 4.8.2 works)

Richard.

>
> Richard

Re: [08/23] Add an alternative splay tree implementation

[Richard Sandiford via Gcc-patches]

Andreas Schwab  writes:
> On Jan 04 2021, Richard Sandiford wrote:
>
>> Andreas Schwab  writes:
>>> That doesn't build with gcc 4.8:
>>
>> Which subversion are you using?
>
> This is 4.8.1.

Hmm, OK.  I guess that raises the question whether “supporting GCC 4.8”
means supporting every patchlevel, or just the latest.

Richard

Re: [08/23] Add an alternative splay tree implementation

[Jeff Law via Gcc-patches]

On 12/16/20 5:29 PM, Richard Sandiford wrote:
> Jeff Law  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  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

Re: [08/23] Add an alternative splay tree implementation

[Andreas Schwab]

On Jan 04 2021, Richard Sandiford wrote:

> Andreas Schwab  writes:
>> That doesn't build with gcc 4.8:
>
> Which subversion are you using?

This is 4.8.1.

Andreas.

-- 
Andreas Schwab, sch...@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: [08/23] Add an alternative splay tree implementation

[Richard Sandiford via Gcc-patches]

Andreas Schwab  writes:
> That doesn't build with gcc 4.8:

Which subversion are you using?  It works for me with stock gcc 4.8.5,
which is what I'd used to test the series for C++ compatiblity.

Richard

>
> In file included from ../../gcc/splay-tree-utils.h:491:0,
>  from ../../gcc/rtl-ssa.h:45,
>  from ../../gcc/fwprop.c:29:
> ../../gcc/splay-tree-utils.tcc:24:1: error: prototype for 'typename 
> base_splay_tree::node_type 
> base_splay_tree::get_child(typename Accessors::node_type, unsigned 
> int)' does not match any in class 'base_splay_tree'
>  base_splay_tree::get_child (node_type node, unsigned int index)
>  ^
> In file included from ../../gcc/rtl-ssa.h:45:0,
>  from ../../gcc/fwprop.c:29:
> ../../gcc/splay-tree-utils.h:125:20: error: candidate is: static typename 
> Accessors::node_type base_splay_tree::get_child(typename 
> Accessors::node_type, unsigned int)
>static node_type get_child (node_type, unsigned int);
> ^
>
> Andreas.

Re: [08/23] Add an alternative splay tree implementation

[Andreas Schwab]

That doesn't build with gcc 4.8:

In file included from ../../gcc/splay-tree-utils.h:491:0,
 from ../../gcc/rtl-ssa.h:45,
 from ../../gcc/fwprop.c:29:
../../gcc/splay-tree-utils.tcc:24:1: error: prototype for 'typename 
base_splay_tree::node_type 
base_splay_tree::get_child(typename Accessors::node_type, unsigned 
int)' does not match any in class 'base_splay_tree'
 base_splay_tree::get_child (node_type node, unsigned int index)
 ^
In file included from ../../gcc/rtl-ssa.h:45:0,
 from ../../gcc/fwprop.c:29:
../../gcc/splay-tree-utils.h:125:20: error: candidate is: static typename 
Accessors::node_type base_splay_tree::get_child(typename 
Accessors::node_type, unsigned int)
   static node_type get_child (node_type, unsigned int);
^

Andreas.

-- 
Andreas Schwab, sch...@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: [08/23] Add an alternative splay tree implementation

[Richard Sandiford via Gcc-patches]

Jeff Law  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  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?

Thanks,
Richard

Re: [08/23] Add an alternative splay tree implementation

[Jeff Law via Gcc-patches]

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  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 :-)

As for the implementation, I've got no real concerns there.  If there's
issues, I'm sure you'll deal with them.

Jeff

[08/23] Add an alternative splay tree implementation

[Richard Sandiford via Gcc-patches]

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  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.
---
 gcc/Makefile.in  |   1 +
 gcc/selftest-run-tests.c |   1 +
 gcc/selftest.h   |   1 +
 gcc/splay-tree-utils.cc  | 264 +++
 gcc/splay-tree-utils.h   | 491 
 gcc/splay-tree-utils.tcc | 960 +++
 gcc/system.h |   3 +
 7 files changed, 1721 insertions(+)
 create mode 100644 gcc/splay-tree-utils.cc
 create mode 100644 gcc/splay-tree-utils.h
 create mode 100644 gcc/splay-tree-utils.tcc

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 978a08f7b04..900bf11b0ba 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1540,6 +1540,7 @@ OBJS = \
sparseset.o \
spellcheck.o \
spellcheck-tree.o \
+   splay-tree-utils.o \
sreal.o \
stack-ptr-mod.o \
statistics.o \
diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c
index 7a89b2df5bd..c0c18ad17ca 100644
--- a/gcc/selftest-run-tests.c
+++ b/gcc/selftest-run-tests.c
@@ -79,6 +79,7 @@ selftest::run_tests ()
   optinfo_emit_json_cc_tests ();
   opt_problem_cc_tests ();
   ordered_hash_map_tests_cc_tests ();
+  splay_tree_cc_tests ();
 
   /* Mid-level data structures.  */
   input_c_tests ();
diff --git a/gcc/selftest.h b/gcc/selftest.h
index 963e074b4d2..b6e4345b19f 100644
--- a/gcc/selftest.h
+++ b/gcc/selftest.h
@@ -256,6 +256,7 @@ extern void selftest_c_tests ();
 extern void simplify_rtx_c_tests ();
 extern void spellcheck_c_tests ();
 extern void spellcheck_tree_c_tests ();
+extern void splay_tree_cc_tests ();
 extern void sreal_c_tests ();
 extern void store_merging_c_tests ();
 extern void tree_c_tests ();
diff --git a/gcc/splay-tree-utils.cc b/gcc/splay-tree-utils.cc
new file mode 100644
index 000..4b2007b8414
--- /dev/null
+++ b/gcc/splay-tree-utils.cc
@@ -0,0 +1,264 @@
+// Splay tree utilities -*- C++ -*-
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of GCC.
+//
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+//
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+// for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3.  If not see
+// .
+
+#define INCLUDE_ALGORITHM
+#define INCLUDE_ARRAY
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include