> Am 09.08.2024 um 19:19 schrieb Richard Sandiford <richard.sandif...@arm.com>:
>
> This patch is an attempt to gauge opinion on one way of fixing PR30920.
>
> The PR points out that the libiberty splay tree implementation does
> not implement the algorithm described by Sleator and Tarjan and has
> unclear complexity bounds. (It's also somewhat dangerous in that
> splay_tree_min and splay_tree_max walk the tree without splaying,
> meaning that they are fully linear in the worst case, rather than
> amortised logarithmic.) These properties have been carried over
> to typed-splay-tree.h.
>
> We could fix those problems directly in the existing implementations,
> and probably should for libiberty. But when I added rtl-ssa, I also
> added a third(!) splay tree implementation: splay-tree-utils.h.
> In response to Jeff's understandable unease about having three
> implementations, I was supposed to go back during the next stage 1
> and reduce it to no more than two. I never did that. :-(
I wonder if typed_splay_tree could wrap around splay-tree-utils. Though the
typed variant is the least used…
> splay-tree-utils.h is so called because rtl-ssa uses splay trees
> in structures that are relatively small and very size-sensitive.
> I therefore wanted to be able to embed the splay tree links directly
> in the structures, rather than pay the penalty of using separate
> nodes with one-way or two-way links between them. There were also
> operations for which it was convenient to treat the splay tree root
> as an explicitly managed cursor, rather than treating the tree as
> a pure ADT. The interface is therefore a bit more low-level than
> for the other implementations.
>
> I wondered whether the same trade-offs might apply to users of
> the libiberty splay trees. The first one I looked at in detail
> was SCC value numbering, which seemed like it would benefit from
> using splay-tree-utils.h directly.
>
> The patch does that. It also adds a couple of new helper routines
> to splay-tree-utils.h.
>
> I don't expect this approach to be the right one for every use
> of splay trees. E.g. splay tree used for omp gimplification would
> certainly need separate nodes.
>
> Tested on aarch64-linux-gnu & x86_64-linux-gnu. OK to install?
Ok
Thanks,
Richard
> Richard
>
>
> gcc/
> * splay-tree-utils.h (rooted_splay_tree::insert_relative)
> (rooted_splay_tree::lookup_le): New functions.
> (rooted_splay_tree::remove_root_and_splay_next): Likewise.
> * splay-tree-utils.h (rooted_splay_tree::insert_relative): New
> function, extracted from...
> (rooted_splay_tree::insert): ...here.
> (rooted_splay_tree::lookup_le): New function.
> (rooted_splay_tree::remove_root_and_splay_next): Likewise.
> * tree-ssa-sccvn.cc (pd_range::m_children): New member variable.
> (vn_walk_cb_data::vn_walk_cb_data): Initialize first_range.
> (vn_walk_cb_data::known_ranges): Use a default_splay_tree.
> (vn_walk_cb_data::~vn_walk_cb_data): Remove freeing of known_ranges.
> (pd_range_compare, pd_range_alloc, pd_range_dealloc): Delete.
> (vn_walk_cb_data::push_partial_def): Rewrite splay tree operations
> to use splay-tree-utils.h.
> * rtl-ssa/accesses.cc (function_info::add_use): Use insert_relative.
> ---
> gcc/rtl-ssa/accesses.cc | 8 +--
> gcc/splay-tree-utils.h | 29 +++++++++++
> gcc/splay-tree-utils.tcc | 69 ++++++++++++++++++++++---
> gcc/tree-ssa-sccvn.cc | 106 +++++++++++++--------------------------
> 4 files changed, 131 insertions(+), 81 deletions(-)
>
> diff --git a/gcc/rtl-ssa/accesses.cc b/gcc/rtl-ssa/accesses.cc
> index 5e9077545a8..ef99759871a 100644
> --- a/gcc/rtl-ssa/accesses.cc
> +++ b/gcc/rtl-ssa/accesses.cc
> @@ -1232,16 +1232,16 @@ function_info::add_use (use_info *use)
> need_use_splay_tree (def);
> int comparison = lookup_use (def->m_use_tree, insn);
> gcc_checking_assert (comparison != 0);
> - splay_tree_node<use_info *> *neighbor = def->m_use_tree.root ();
> + use_info *neighbor = def->m_use_tree.root ()->value ();
>
> // If USE comes before NEIGHBOR, insert USE to NEIGHBOR's left,
> // otherwise insert USE to NEIGHBOR's right.
> auto *use_node = allocate<splay_tree_node<use_info *>> (use);
> - def->m_use_tree.insert_child (neighbor, comparison > 0, use_node);
> + def->m_use_tree.insert_relative (comparison, use_node);
> if (comparison > 0)
> - insert_use_after (use, neighbor->value ());
> + insert_use_after (use, neighbor);
> else
> - insert_use_before (use, neighbor->value ());
> + insert_use_before (use, neighbor);
> }
>
> void
> diff --git a/gcc/splay-tree-utils.h b/gcc/splay-tree-utils.h
> index 8344808f6d1..9526e0ba336 100644
> --- a/gcc/splay-tree-utils.h
> +++ b/gcc/splay-tree-utils.h
> @@ -185,6 +185,21 @@ public:
> template<typename Comparator>
> bool insert (node_type new_node, Comparator compare);
>
> + // Insert NEW_NODE into the splay tree. If the tree is currently
> non-empty,
> + // COMPARISON is < 0 if NEW_NODE comes immediate before the current root,
> + // or > 0 if NEW_NODE comes immediately after the current root.
> + //
> + // On return, NEW_NODE is the root of the tree.
> + //
> + // For example, this can be used in the construct:
> + //
> + // int comparison = tree.lookup (...);
> + // if (comparison != 0)
> + // tree.insert_relative (comparison, create_new_node ());
> + //
> + // Complexity: O(1)
> + void insert_relative (int comparison, node_type new_node);
> +
> // Insert NEW_NODE into the splay tree, given that NEW_NODE is the
> // maximum node of the new tree. On return, NEW_NODE is also the
> // root of the tree.
> @@ -212,6 +227,14 @@ public:
> // Otherwise amortized O(log N), worst-cast O(N).
> void remove_root ();
>
> + // Remove the root node of the splay tree. If the root node was not
> + // the maximum node, bring the next node to the root and return true.
> + // Return false otherwise.
> + //
> + // Complexity: O(1) if removing the maximum node. Otherwise amortized
> + // O(log N), worst-cast O(N).
> + bool remove_root_and_splay_next ();
> +
> // Split the left child of the current root out into a separate tree
> // and return the new tree.
> rooted_splay_tree split_before_root ();
> @@ -326,6 +349,12 @@ public:
> int lookup (LeftPredicate want_something_smaller,
> RightPredicate want_something_bigger);
>
> + // Like lookup, but always pick a node that is no bigger than the one
> + // being searched for, if such a node exists.
> + template<typename LeftPredicate, typename RightPredicate>
> + int lookup_le (LeftPredicate want_something_smaller,
> + RightPredicate want_something_bigger);
> +
> // Keep the ability to print subtrees.
> using parent::print;
>
> diff --git a/gcc/splay-tree-utils.tcc b/gcc/splay-tree-utils.tcc
> index 5c36bb55f78..6118233a5f6 100644
> --- a/gcc/splay-tree-utils.tcc
> +++ b/gcc/splay-tree-utils.tcc
> @@ -340,15 +340,30 @@ rooted_splay_tree<Accessors>::insert (node_type
> new_node, Comparator compare)
> if (comparison == 0)
> return false;
>
> - // Insert NEW_NODE before M_ROOT if COMPARISON < 0 and after M_ROOT
> - // otherwise.
> - set_child (new_node, comparison < 0, m_root);
> - set_child (new_node, comparison > 0, get_child (m_root, comparison > 0));
> - set_child (m_root, comparison > 0, nullptr);
> - m_root = new_node;
> + insert_relative (comparison, new_node);
> return true;
> }
>
> +// See the comment above the declaration.
> +template<typename Accessors>
> +inline void
> +rooted_splay_tree<Accessors>::insert_relative (int comparison,
> + node_type new_node)
> +{
> + gcc_checking_assert (!get_child (new_node, 0)
> + && !get_child (new_node, 1)
> + && (!m_root || comparison != 0));
> + if (m_root)
> + {
> + // Insert NEW_NODE before M_ROOT if COMPARISON < 0 and after M_ROOT
> + // otherwise.
> + set_child (new_node, comparison < 0, m_root);
> + set_child (new_node, comparison > 0, get_child (m_root, comparison >
> 0));
> + set_child (m_root, comparison > 0, node_type ());
> + }
> + m_root = new_node;
> +}
> +
> // See the comment above the declaration.
> template<typename Accessors>
> inline void
> @@ -398,6 +413,35 @@ rooted_splay_tree<Accessors>::remove_root ()
> set_child (node, 1, node_type ());
> }
>
> +// See the comment above the declaration.
> +template<typename Accessors>
> +inline bool
> +rooted_splay_tree<Accessors>::remove_root_and_splay_next ()
> +{
> + node_type node = m_root;
> + node_type right = get_child (node, 1);
> + if (right)
> + {
> + // Bring the minimum right-hand node to the root.
> + if (get_child (right, 0))
> + {
> + right = parent::template splay_limit<0> (right);
> + gcc_checking_assert (!get_child (right, 0));
> + }
> + set_child (right, 0, get_child (node, 0));
> + m_root = right;
> + }
> + else
> + m_root = get_child (node, 0);
> + if (m_root)
> + set_parent (m_root, node_type ());
> +
> + // Clear the links from NODE. Its parent is already node_type ().
> + set_child (node, 0, node_type ());
> + set_child (node, 1, node_type ());
> + return right;
> +}
> +
> // See the comment above the declaration.
> template<typename Accessors>
> inline rooted_splay_tree<Accessors>
> @@ -730,6 +774,19 @@ rooted_splay_tree<Accessors>::lookup (LeftPredicate
> want_something_smaller,
> return result;
> }
>
> +// See the comment above the declaration.
> +template<typename Accessors>
> +template<typename LeftPredicate, typename RightPredicate>
> +int
> +rooted_splay_tree<Accessors>::lookup_le (LeftPredicate
> want_something_smaller,
> + RightPredicate want_something_bigger)
> +{
> + int comparison = lookup (want_something_smaller, want_something_bigger);
> + if (comparison < 0 && splay_prev_node ())
> + comparison = 1;
> + return comparison;
> +}
> +
> // See the comment above the declaration.
> template<typename Accessors>
> template<typename Printer>
> diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc
> index 0639ba426ff..4370d09d9d8 100644
> --- a/gcc/tree-ssa-sccvn.cc
> +++ b/gcc/tree-ssa-sccvn.cc
> @@ -21,7 +21,6 @@ along with GCC; see the file COPYING3. If not see
> #include "config.h"
> #include "system.h"
> #include "coretypes.h"
> -#include "splay-tree.h"
> #include "backend.h"
> #include "rtl.h"
> #include "tree.h"
> @@ -33,6 +32,7 @@ along with GCC; see the file COPYING3. If not see
> #include "emit-rtl.h"
> #include "cgraph.h"
> #include "gimple-pretty-print.h"
> +#include "splay-tree-utils.h"
> #include "alias.h"
> #include "fold-const.h"
> #include "stor-layout.h"
> @@ -1832,6 +1832,7 @@ struct pd_range
> {
> HOST_WIDE_INT offset;
> HOST_WIDE_INT size;
> + pd_range *m_children[2];
> };
>
> struct pd_data
> @@ -1853,8 +1854,8 @@ struct vn_walk_cb_data
> mask (mask_), masked_result (NULL_TREE), same_val (NULL_TREE),
> vn_walk_kind (vn_walk_kind_),
> tbaa_p (tbaa_p_), redundant_store_removal_p
> (redundant_store_removal_p_),
> - saved_operands (vNULL), first_set (-2), first_base_set (-2),
> - known_ranges (NULL)
> + saved_operands (vNULL), first_range (), first_set (-2),
> + first_base_set (-2)
> {
> if (!last_vuse_ptr)
> last_vuse_ptr = &last_vuse;
> @@ -1924,7 +1925,7 @@ struct vn_walk_cb_data
> pd_range first_range;
> alias_set_type first_set;
> alias_set_type first_base_set;
> - splay_tree known_ranges;
> + default_splay_tree<pd_range *> known_ranges;
> obstack ranges_obstack;
> static constexpr HOST_WIDE_INT bufsize = 64;
> };
> @@ -1932,10 +1933,7 @@ struct vn_walk_cb_data
> vn_walk_cb_data::~vn_walk_cb_data ()
> {
> if (known_ranges)
> - {
> - splay_tree_delete (known_ranges);
> - obstack_free (&ranges_obstack, NULL);
> - }
> + obstack_free (&ranges_obstack, NULL);
> saved_operands.release ();
> }
>
> @@ -1961,32 +1959,6 @@ vn_walk_cb_data::finish (alias_set_type set,
> alias_set_type base_set, tree val)
> vr->type, operands, val);
> }
>
> -/* pd_range splay-tree helpers. */
> -
> -static int
> -pd_range_compare (splay_tree_key offset1p, splay_tree_key offset2p)
> -{
> - HOST_WIDE_INT offset1 = *(HOST_WIDE_INT *)offset1p;
> - HOST_WIDE_INT offset2 = *(HOST_WIDE_INT *)offset2p;
> - if (offset1 < offset2)
> - return -1;
> - else if (offset1 > offset2)
> - return 1;
> - return 0;
> -}
> -
> -static void *
> -pd_tree_alloc (int size, void *data_)
> -{
> - vn_walk_cb_data *data = (vn_walk_cb_data *)data_;
> - return obstack_alloc (&data->ranges_obstack, size);
> -}
> -
> -static void
> -pd_tree_dealloc (void *, void *)
> -{
> -}
> -
> /* Push PD to the vector of partial definitions returning a
> value when we are ready to combine things with VUSE, SET and MAXSIZEI,
> NULL when we want to continue looking for partial defs or -1
> @@ -2055,51 +2027,43 @@ vn_walk_cb_data::push_partial_def (pd_data pd,
> /* ??? Optimize the case where the 2nd partial def completes
> things. */
> gcc_obstack_init (&ranges_obstack);
> - known_ranges = splay_tree_new_with_allocator (pd_range_compare, 0, 0,
> - pd_tree_alloc,
> - pd_tree_dealloc, this);
> - splay_tree_insert (known_ranges,
> - (splay_tree_key)&first_range.offset,
> - (splay_tree_value)&first_range);
> - }
> -
> - pd_range newr = { pd.offset, pd.size };
> - splay_tree_node n;
> - /* Lookup the predecessor of offset + 1 and see if we need to merge.
> */
> - HOST_WIDE_INT loffset = newr.offset + 1;
> - if ((n = splay_tree_predecessor (known_ranges,
> (splay_tree_key)&loffset))
> - && ((r = (pd_range *)n->value), true)
> + known_ranges.insert_max_node (&first_range);
> + }
> + /* Lookup the offset and see if we need to merge. */
> + int comparison = known_ranges.lookup_le
> + ([&] (pd_range *r) { return pd.offset < r->offset; },
> + [&] (pd_range *r) { return pd.offset > r->offset; });
> + r = known_ranges.root ();
> + if (comparison >= 0
> && ranges_known_overlap_p (r->offset, r->size + 1,
> - newr.offset, newr.size))
> + pd.offset, pd.size))
> {
> /* Ignore partial defs already covered. Here we also drop shadowed
> clobbers arriving here at the floor. */
> - if (known_subrange_p (newr.offset, newr.size, r->offset, r->size))
> + if (known_subrange_p (pd.offset, pd.size, r->offset, r->size))
> return NULL;
> - r->size
> - = MAX (r->offset + r->size, newr.offset + newr.size) - r->offset;
> + r->size = MAX (r->offset + r->size, pd.offset + pd.size) - r->offset;
> }
> else
> {
> - /* newr.offset wasn't covered yet, insert the range. */
> - r = XOBNEW (&ranges_obstack, pd_range);
> - *r = newr;
> - splay_tree_insert (known_ranges, (splay_tree_key)&r->offset,
> - (splay_tree_value)r);
> - }
> - /* Merge r which now contains newr and is a member of the splay tree
> with
> - adjacent overlapping ranges. */
> - pd_range *rafter;
> - while ((n = splay_tree_successor (known_ranges,
> - (splay_tree_key)&r->offset))
> - && ((rafter = (pd_range *)n->value), true)
> - && ranges_known_overlap_p (r->offset, r->size + 1,
> - rafter->offset, rafter->size))
> - {
> - r->size = MAX (r->offset + r->size,
> - rafter->offset + rafter->size) - r->offset;
> - splay_tree_remove (known_ranges, (splay_tree_key)&rafter->offset);
> + /* pd.offset wasn't covered yet, insert the range. */
> + void *addr = XOBNEW (&ranges_obstack, pd_range);
> + r = new (addr) pd_range { pd.offset, pd.size, {} };
> + known_ranges.insert_relative (comparison, r);
> }
> + /* Merge r which now contains pd's range and is a member of the splay
> + tree with adjacent overlapping ranges. */
> + if (known_ranges.splay_next_node ())
> + do
> + {
> + pd_range *rafter = known_ranges.root ();
> + if (!ranges_known_overlap_p (r->offset, r->size + 1,
> + rafter->offset, rafter->size))
> + break;
> + r->size = MAX (r->offset + r->size,
> + rafter->offset + rafter->size) - r->offset;
> + }
> + while (known_ranges.remove_root_and_splay_next ());
> /* If we get a clobber, fail. */
> if (TREE_CLOBBER_P (pd.rhs))
> return (void *)-1;
> @@ -2109,7 +2073,7 @@ vn_walk_cb_data::push_partial_def (pd_data pd,
> partial_defs.safe_push (pd);
> }
>
> - /* Now we have merged newr into the range tree. When we have covered
> + /* Now we have merged pd's range into the range tree. When we have covered
> [offseti, sizei] then the tree will contain exactly one node which has
> the desired properties and it will be 'r'. */
> if (!known_subrange_p (0, maxsizei, r->offset, r->size))
> --
> 2.25.1
>
