https://gcc.gnu.org/g:9ab8681db6c7736357a8713afec7c7b09080cba9
commit r15-2884-g9ab8681db6c7736357a8713afec7c7b09080cba9
Author: Richard Sandiford <richard.sandif...@arm.com>
Date: Mon Aug 12 10:52:29 2024 +0100
Use splay-tree-utils.h in tree-ssa-sccvn [PR30920]
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. :-(
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.
gcc/
PR other/30920
* 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.tcc (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.
Diff:
---
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 5e9077545a81..ef99759871aa 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 8344808f6d19..9526e0ba3363 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 5c36bb55f78b..6118233a5f6b 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 0639ba426ff5..4370d09d9d8c 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))
