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.

1 files changed, 63 insertions, 6 deletions

diff --git a/gcc/splay-tree-utils.tcc b/gcc/splay-tree-utils.tcc
index 5c36bb5..6118233 100644
--- a/gcc/splay-tree-utils.tcc
+++ b/gcc/splay-tree-utils.tcc
@@ -340,18 +340,33 @@ 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
 rooted_splay_tree<Accessors>::insert_max_node (node_type new_node)
 {
   gcc_checking_assert (!get_child (new_node, 0) && !get_child (new_node, 1));
@@ -400,6 +415,35 @@ rooted_splay_tree<Accessors>::remove_root ()
 
 // 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>
 rooted_splay_tree<Accessors>::split_before_root ()
 {
@@ -732,6 +776,19 @@ rooted_splay_tree<Accessors>::lookup (LeftPredicate want_something_smaller,
 
 // 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>
 inline void
 rooted_splay_tree<Accessors>::print (pretty_printer *pp, Printer printer) const