aboutsummaryrefslogtreecommitdiff
path: root/gcc
diff options
context:
space:
mode:
Diffstat (limited to 'gcc')
-rw-r--r--gcc/rtl-ssa/accesses.cc8
-rw-r--r--gcc/splay-tree-utils.h29
-rw-r--r--gcc/splay-tree-utils.tcc69
-rw-r--r--gcc/tree-ssa-sccvn.cc106
4 files changed, 131 insertions, 81 deletions
diff --git a/gcc/rtl-ssa/accesses.cc b/gcc/rtl-ssa/accesses.cc
index 5e90775..ef99759 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 8344808..9526e0b 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 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
diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc
index 0639ba4..4370d09 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))
generated by cgit v1.1 at 2025-04-02 10:44:46 +0000