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.

0 files changed, 0 insertions, 0 deletions