----------------------------------------
> From: stevenb....@gmail.com
> Date: Mon, 9 Mar 2015 23:59:52 +0100
> Subject: Re: Proposal for adding splay_tree_find (to find elements without
> updating the nodes).
> To: hiradi...@msn.com
> CC: gcc@gcc.gnu.org
>
> On Mon, Mar 9, 2015 at 7:59 PM, vax mzn wrote:
>> w.r.t, https://gcc.gnu.org/wiki/Speedup_areas where we want to improve the
>> performance of splay trees.
>>
>> The function `splay_tree_node splay_tree_lookup (splay_tree,
>> splay_tree_key);'
>> updates the nodes every time a lookup is done.
>>
>> IIUC, There are places where we call this function in a loop i.e., we lookup
>> different elements every time.
>> e.g.,
>> In this exaple we are looking for a different `t' in each iteration.
>
>
> If that's really true, then a splay tree is a horrible choice of data
> structure. The splay tree will simply degenerate to a linked list. The
> right thing to do would be, not to "break" one of the key features of
> splay trees (i.e. the latest lookup is always on top), but to use
> another data structure.
>
> Ciao!
> Steven
So I have this patch which replaces splay_tree_lookup with a new function
splay_tree_find at some places.
I hope this is helpful.
commit 64f203f36661efd95958474f31b588a134dedb41
Author: Aditya <hiradi...@msn.com>
Date: Mon Mar 9 22:47:04 2015 -0500
add splay_tree_find for finding elements without updating the tree
diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index d822913..1053eee 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -1093,7 +1093,7 @@ gimplify_bind_expr (tree *expr_p, gimple_seq *pre_p)
/* Mark variable as local. */
if (ctx && !DECL_EXTERNAL (t)
&& (! DECL_SEEN_IN_BIND_EXPR_P (t)
- || splay_tree_lookup (ctx->variables,
+ || splay_tree_find (ctx->variables,
(splay_tree_key) t) == NULL))
{
if (ctx->region_type == ORT_SIMD
@@ -5529,7 +5529,7 @@ omp_firstprivatize_variable (struct gimplify_omp_ctx
*ctx, tree decl)
do
{
- n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
+ n = splay_tree_find (ctx->variables, (splay_tree_key)decl);
if (n != NULL)
{
if (n->value & GOVD_SHARED)
@@ -6428,7 +6428,7 @@ gimplify_adjust_omp_clauses_1 (splay_tree_node n, void
*data)
while (ctx != NULL)
{
splay_tree_node on
- = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+ = splay_tree_find (ctx->variables, (splay_tree_key) decl);
if (on && (on->value & (GOVD_FIRSTPRIVATE | GOVD_LASTPRIVATE
| GOVD_PRIVATE | GOVD_REDUCTION
| GOVD_LINEAR | GOVD_MAP)) != 0)
@@ -6529,7 +6529,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree
*list_p)
case OMP_CLAUSE_FIRSTPRIVATE:
case OMP_CLAUSE_LINEAR:
decl = OMP_CLAUSE_DECL (c);
- n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+ n = splay_tree_find (ctx->variables, (splay_tree_key) decl);
remove = !(n->value & GOVD_SEEN);
if (! remove)
{
@@ -6551,7 +6551,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree
*list_p)
if (ctx->outer_context->combined_loop
&& !OMP_CLAUSE_LINEAR_NO_COPYIN (c))
{
- n = splay_tree_lookup (ctx->outer_context->variables,
+ n = splay_tree_find (ctx->outer_context->variables,
(splay_tree_key) decl);
if (n == NULL
|| (n->value & GOVD_DATA_SHARE_CLASS) == 0)
@@ -6578,7 +6578,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree
*list_p)
/* Make sure OMP_CLAUSE_LASTPRIVATE_FIRSTPRIVATE is set to
accurately reflect the presence of a FIRSTPRIVATE clause. */
decl = OMP_CLAUSE_DECL (c);
- n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+ n = splay_tree_find (ctx->variables, (splay_tree_key) decl);
OMP_CLAUSE_LASTPRIVATE_FIRSTPRIVATE (c)
= (n->value & GOVD_FIRSTPRIVATE) != 0;
break;
@@ -6587,7 +6587,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree
*list_p)
decl = OMP_CLAUSE_DECL (c);
if (!is_global_var (decl))
{
- n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+ n = splay_tree_find (ctx->variables, (splay_tree_key) decl);
remove = n == NULL || !(n->value & GOVD_SEEN);
if (!remove && TREE_CODE (TREE_TYPE (decl)) == POINTER_TYPE)
{
@@ -6600,7 +6600,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree
*list_p)
for (octx = ctx->outer_context; octx;
octx = octx->outer_context)
{
- n = splay_tree_lookup (octx->variables,
+ n = splay_tree_find (octx->variables,
(splay_tree_key) decl);
if (n == NULL)
continue;
@@ -6619,7 +6619,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree
*list_p)
}
else if (TREE_CODE (TREE_TYPE (decl)) == ARRAY_TYPE)
{
- n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+ n = splay_tree_find (ctx->variables, (splay_tree_key) decl);
if (n != NULL && (n->value & GOVD_DATA_SHARE_CLASS) != 0)
remove = true;
}
@@ -6629,7 +6629,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree
*list_p)
decl = OMP_CLAUSE_DECL (c);
if (!DECL_P (decl))
break;
- n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+ n = splay_tree_find (ctx->variables, (splay_tree_key) decl);
if (ctx->region_type == ORT_TARGET && !(n->value & GOVD_SEEN))
remove = true;
else if (DECL_SIZE (decl)
diff --git a/gcc/tree-dump.c b/gcc/tree-dump.c
index 620b391..f942f14 100644
--- a/gcc/tree-dump.c
+++ b/gcc/tree-dump.c
@@ -113,7 +113,7 @@ queue_and_dump_index (dump_info_p di, const char *field,
const_tree t, int flags
return;
/* See if we've already queued or dumped this node. */
- n = splay_tree_lookup (di->nodes, (splay_tree_key) t);
+ n = splay_tree_find (di->nodes, (splay_tree_key) t);
if (n)
index = ((dump_node_info_p) n->value)->index;
else
diff --git a/include/splay-tree.h b/include/splay-tree.h
index ec48a1f..a73a2cf 100644
--- a/include/splay-tree.h
+++ b/include/splay-tree.h
@@ -141,6 +141,7 @@ extern splay_tree_node splay_tree_insert (splay_tree,
splay_tree_key,
splay_tree_value);
extern void splay_tree_remove (splay_tree, splay_tree_key);
+extern splay_tree_node splay_tree_find (splay_tree sp, splay_tree_key key);
extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key);
extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key);
extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key);
diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c
index 12bfa8b..7cdf5d5 100644
--- a/libiberty/splay-tree.c
+++ b/libiberty/splay-tree.c
@@ -198,6 +198,38 @@ splay_tree_splay (splay_tree sp, splay_tree_key key)
} while (1);
}
+/* Simple binary tree search without any sort of update. This is useful when
+ we do not care about locality. e.g., searching nodes in an loop */
+
+splay_tree_node
+splay_tree_find (splay_tree sp, splay_tree_key key)
+{
+ if (sp->root == 0)
+ return;
+
+ int cmp;
+ splay_tree_node n, c;
+ c = sp->root;
+
+ do {
+
+ n = c;
+ cmp = (*sp->comp) (key, n->key);
+
+ /* Found. */
+ if (cmp == 0)
+ return n;
+
+ /* Left or right? If no child, then we're done. */
+ if (cmp < 0)
+ c = n->left;
+ else
+ c = n->right;
+ if (!c)
+ return 0;
+ } while (1);
+}
+
/* Call FN, passing it the DATA, for every node below NODE, all of
which are from SP, following an in-order traversal. If FN every
returns a non-zero value, the iteration ceases immediately, and the
