https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30920
--- Comment #7 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The trunk branch has been updated by Richard Sandiford <rsand...@gcc.gnu.org>: 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.
