| Message ID | mptzfplvcld.fsf@arm.com |
|---|---|
| State | New |
| Headers | show |
| Series | Use splay-tree-utils.h in tree-ssa-sccvn [PR30920] | expand |
> Am 09.08.2024 um 19:19 schrieb Richard Sandiford <richard.sandiford@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 >
Richard Biener <richard.guenther@gmail.com> writes: >> Am 09.08.2024 um 19:19 schrieb Richard Sandiford <richard.sandiford@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… Yeah, that's probably going to be what happens for most of them. One of the things I'm trying to work out by going through them is whether we need both associative and non-associative containers (like for hash_table/hash_map) or whether the current associative-only approach is best. Also not sure yet how best to handle memory management. Richard > >> 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 >>
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))