* Remove splay_tree from gimplify.c
@ 2015-05-18 2:52 Aditya K
2015-05-27 16:59 ` Jeff Law
0 siblings, 1 reply; 4+ messages in thread
From: Aditya K @ 2015-05-18 2:52 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 24939 bytes --]
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.
gcc/gimplify.c:1096: splay_tree_lookup (ctx->variables, (splay_tree_key) t) == NULL)
Here, we change the tree itself `ctx'
gcc/gimplify.c:5532: n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
I think we don't need to update the tree in these cases at least.
I have pasted the patch which removes splay_tree with hash_map. Another patch (attached) removes splay_tree with std::map.
Please review the patches.
Thanks,
-Aditya
gcc/ChangeLog:
2015-05-17 hiraditya <hiraditya@msn.com>
Remove splay_tree from gimplify.c
* gimplify.c (struct gimplify_omp_ctx): Replaced splay_tree with hash_map
(splay_tree_compare_decl_uid): Likewise
(new_omp_context): Likewise
(delete_omp_context): Likewise
(gimplify_bind_expr): Likewise
(omp_firstprivatize_variable): Likewise
(omp_add_variable): Likewise
(omp_notice_threadprivate_variable): Likewise
(omp_notice_variable): Likewise
(omp_is_private): Likewise
(omp_check_private): Likewise
(gimplify_adjust_omp_clauses_1): Likewise
(gimplify_adjust_omp_clauses): Likewise
(gimplify_omp_for): Likewise
* hash-map.h: Added typedefs.
diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index 4846478..4454ec4 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -92,6 +92,20 @@ along with GCC; see the file COPYING3. If not see
#include "tree-pass.h" /* FIXME: only for PROP_gimple_any */
#include "builtins.h"
+struct tree_compare_decl_uid : default_hashmap_traits {
+ static inline hashval_t hash(tree t)
+ {
+ return iterative_hash_expr(t, 0);
+ }
+
+ static inline bool equal_keys(const tree &xa, const tree &xb)
+ {
+ return DECL_UID (xa) == DECL_UID (xb);
+ }
+};
+
+typedef hash_map<tree, unsigned, tree_compare_decl_uid> gimplify_tree_t;
+
enum gimplify_omp_var_data
{
GOVD_SEEN = 1,
@@ -166,7 +180,7 @@ struct gimplify_ctx
struct gimplify_omp_ctx
{
struct gimplify_omp_ctx *outer_context;
- splay_tree variables;
+ gimplify_tree_t *variables;
hash_set<tree> *privatized_types;
location_t location;
enum omp_clause_default_kind default_kind;
@@ -364,17 +378,6 @@ gimple_pop_condition (gimple_seq *pre_p)
}
}
-/* A stable comparison routine for use with splay trees and DECLs. */
-
-static int
-splay_tree_compare_decl_uid (splay_tree_key xa, splay_tree_key xb)
-{
- tree a = (tree) xa;
- tree b = (tree) xb;
-
- return DECL_UID (a) - DECL_UID (b);
-}
-
/* Create a new omp construct that deals with variable remapping. */
static struct gimplify_omp_ctx *
@@ -384,7 +387,7 @@ new_omp_context (enum omp_region_type region_type)
c = XCNEW (struct gimplify_omp_ctx);
c->outer_context = gimplify_omp_ctxp;
- c->variables = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
+ c->variables = new gimplify_tree_t;
c->privatized_types = new hash_set<tree>;
c->location = input_location;
c->region_type = region_type;
@@ -401,7 +404,7 @@ new_omp_context (enum omp_region_type region_type)
static void
delete_omp_context (struct gimplify_omp_ctx *c)
{
- splay_tree_delete (c->variables);
+ delete c->variables;
delete c->privatized_types;
XDELETE (c);
}
@@ -1093,8 +1096,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_key) t) == NULL))
+ || ctx->variables->get(t) == NULL))
{
if (ctx->region_type == ORT_SIMD
&& TREE_ADDRESSABLE (t)
@@ -5550,20 +5552,20 @@ gimplify_stmt (tree *stmt_p, gimple_seq *seq_p)
void
omp_firstprivatize_variable (struct gimplify_omp_ctx *ctx, tree decl)
{
- splay_tree_node n;
+ gimplify_tree_t::data_type *n;
if (decl == NULL || !DECL_P (decl))
return;
do
{
- n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
+ n = ctx->variables->get(decl);
if (n != NULL)
{
- if (n->value & GOVD_SHARED)
- n->value = GOVD_FIRSTPRIVATE | (n->value & GOVD_SEEN);
- else if (n->value & GOVD_MAP)
- n->value |= GOVD_MAP_TO_ONLY;
+ if (*n & GOVD_SHARED)
+ *n = GOVD_FIRSTPRIVATE | (*n & GOVD_SEEN);
+ else if (*n & GOVD_MAP)
+ *n |= GOVD_MAP_TO_ONLY;
else
return;
}
@@ -5640,7 +5642,7 @@ omp_firstprivatize_type_sizes (struct gimplify_omp_ctx *ctx, tree type)
static void
omp_add_variable (struct gimplify_omp_ctx *ctx, tree decl, unsigned int flags)
{
- splay_tree_node n;
+ gimplify_tree_t::data_type *n;
unsigned int nflags;
tree t;
@@ -5653,19 +5655,19 @@ omp_add_variable (struct gimplify_omp_ctx *ctx, tree decl, unsigned int flags)
|| TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (decl)))
flags |= GOVD_SEEN;
- n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
- if (n != NULL && n->value != GOVD_ALIGNED)
+ n = ctx->variables->get(decl);
+ if (n != NULL && *n != GOVD_ALIGNED)
{
/* We shouldn't be re-adding the decl with the same data
sharing class. */
- gcc_assert ((n->value & GOVD_DATA_SHARE_CLASS & flags) == 0);
+ gcc_assert ((*n & GOVD_DATA_SHARE_CLASS & flags) == 0);
/* The only combination of data sharing classes we should see is
FIRSTPRIVATE and LASTPRIVATE. */
- nflags = n->value | flags;
+ nflags = *n | flags;
gcc_assert ((nflags & GOVD_DATA_SHARE_CLASS)
== (GOVD_FIRSTPRIVATE | GOVD_LASTPRIVATE)
|| (flags & GOVD_DATA_SHARE_CLASS) == 0);
- n->value = nflags;
+ *n = nflags;
return;
}
@@ -5734,9 +5736,9 @@ omp_add_variable (struct gimplify_omp_ctx *ctx, tree decl, unsigned int flags)
}
if (n != NULL)
- n->value |= flags;
+ *n |= flags;
else
- splay_tree_insert (ctx->variables, (splay_tree_key)decl, flags);
+ ctx->variables->put(decl, flags);
}
/* Notice a threadprivate variable DECL used in OMP context CTX.
@@ -5748,36 +5750,36 @@ static bool
omp_notice_threadprivate_variable (struct gimplify_omp_ctx *ctx, tree decl,
tree decl2)
{
- splay_tree_node n;
+ gimplify_tree_t::data_type *n;
struct gimplify_omp_ctx *octx;
for (octx = ctx; octx; octx = octx->outer_context)
if (octx->region_type == ORT_TARGET)
{
- n = splay_tree_lookup (octx->variables, (splay_tree_key)decl);
+ n = octx->variables->get(decl);
if (n == NULL)
{
error ("threadprivate variable %qE used in target region",
DECL_NAME (decl));
error_at (octx->location, "enclosing target region");
- splay_tree_insert (octx->variables, (splay_tree_key)decl, 0);
+ octx->variables->put(decl, 0);
}
if (decl2)
- splay_tree_insert (octx->variables, (splay_tree_key)decl2, 0);
+ octx->variables->put(decl2, 0);
}
if (ctx->region_type != ORT_UNTIED_TASK)
return false;
- n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
+ n = ctx->variables->get(decl);
if (n == NULL)
{
error ("threadprivate variable %qE used in untied task",
DECL_NAME (decl));
error_at (ctx->location, "enclosing task");
- splay_tree_insert (ctx->variables, (splay_tree_key)decl, 0);
+ ctx->variables->put(decl, 0);
}
if (decl2)
- splay_tree_insert (ctx->variables, (splay_tree_key)decl2, 0);
+ ctx->variables->put(decl2, 0);
return false;
}
@@ -5790,7 +5792,7 @@ omp_notice_threadprivate_variable (struct gimplify_omp_ctx *ctx, tree decl,
static bool
omp_notice_variable (struct gimplify_omp_ctx *ctx, tree decl, bool in_code)
{
- splay_tree_node n;
+ gimplify_tree_t::data_type *n;
unsigned flags = in_code ? GOVD_SEEN : 0;
bool ret = false, shared;
@@ -5812,7 +5814,7 @@ omp_notice_variable (struct gimplify_omp_ctx *ctx, tree decl, bool in_code)
}
}
- n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
+ n = ctx->variables->get(decl);
if (ctx->region_type == ORT_TARGET)
{
ret = lang_hooks.decls.omp_disregard_value_expr (decl, true);
@@ -5830,9 +5832,9 @@ omp_notice_variable (struct gimplify_omp_ctx *ctx, tree decl, bool in_code)
else
{
/* If nothing changed, there's nothing left to do. */
- if ((n->value & flags) == flags)
+ if ((*n & flags) == flags)
return ret;
- n->value |= flags;
+ *n |= flags;
}
goto do_outer;
}
@@ -5895,12 +5897,12 @@ omp_notice_variable (struct gimplify_omp_ctx *ctx, tree decl, bool in_code)
omp_notice_variable (ctx->outer_context, decl, in_code);
for (octx = ctx->outer_context; octx; octx = octx->outer_context)
{
- splay_tree_node n2;
+ gimplify_tree_t::data_type *n2;
if ((octx->region_type & (ORT_TARGET_DATA | ORT_TARGET)) != 0)
continue;
- n2 = splay_tree_lookup (octx->variables, (splay_tree_key) decl);
- if (n2 && (n2->value & GOVD_DATA_SHARE_CLASS) != GOVD_SHARED)
+ n2 = octx->variables->get(decl);
+ if (n2 && (*n2 & GOVD_DATA_SHARE_CLASS) != GOVD_SHARED)
{
flags |= GOVD_FIRSTPRIVATE;
break;
@@ -5935,28 +5937,29 @@ omp_notice_variable (struct gimplify_omp_ctx *ctx, tree decl, bool in_code)
goto do_outer;
}
- if ((n->value & (GOVD_SEEN | GOVD_LOCAL)) == 0
+ if ((*n & (GOVD_SEEN | GOVD_LOCAL)) == 0
&& (flags & (GOVD_SEEN | GOVD_LOCAL)) == GOVD_SEEN
&& DECL_SIZE (decl)
&& TREE_CODE (DECL_SIZE (decl)) != INTEGER_CST)
{
- splay_tree_node n2;
+ gimplify_tree_t::data_type *n2;
tree t = DECL_VALUE_EXPR (decl);
gcc_assert (TREE_CODE (t) == INDIRECT_REF);
t = TREE_OPERAND (t, 0);
gcc_assert (DECL_P (t));
- n2 = splay_tree_lookup (ctx->variables, (splay_tree_key) t);
- n2->value |= GOVD_SEEN;
+ n2 = ctx->variables->get(t);
+ gcc_assert(n2);
+ *n2 |= GOVD_SEEN;
}
- shared = ((flags | n->value) & GOVD_SHARED) != 0;
+ shared = ((flags | *n) & GOVD_SHARED) != 0;
ret = lang_hooks.decls.omp_disregard_value_expr (decl, shared);
/* If nothing changed, there's nothing left to do. */
- if ((n->value & flags) == flags)
+ if ((*n & flags) == flags)
return ret;
- flags |= n->value;
- n->value = flags;
+ flags |= *n;
+ *n = flags;
do_outer:
/* If the variable is private in the current context, then we don't
@@ -5975,12 +5978,12 @@ omp_notice_variable (struct gimplify_omp_ctx *ctx, tree decl, bool in_code)
static bool
omp_is_private (struct gimplify_omp_ctx *ctx, tree decl, int simd)
{
- splay_tree_node n;
+ gimplify_tree_t::data_type *n;
- n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
+ n = ctx->variables->get(decl);
if (n != NULL)
{
- if (n->value & GOVD_SHARED)
+ if (*n & GOVD_SHARED)
{
if (ctx == gimplify_omp_ctxp)
{
@@ -5990,30 +5993,30 @@ omp_is_private (struct gimplify_omp_ctx *ctx, tree decl, int simd)
else
error ("iteration variable %qE should be private",
DECL_NAME (decl));
- n->value = GOVD_PRIVATE;
+ *n = GOVD_PRIVATE;
return true;
}
else
return false;
}
- else if ((n->value & GOVD_EXPLICIT) != 0
+ else if ((*n & GOVD_EXPLICIT) != 0
&& (ctx == gimplify_omp_ctxp
|| (ctx->region_type == ORT_COMBINED_PARALLEL
&& gimplify_omp_ctxp->outer_context == ctx)))
{
- if ((n->value & GOVD_FIRSTPRIVATE) != 0)
+ if ((*n & GOVD_FIRSTPRIVATE) != 0)
error ("iteration variable %qE should not be firstprivate",
DECL_NAME (decl));
- else if ((n->value & GOVD_REDUCTION) != 0)
+ else if ((*n & GOVD_REDUCTION) != 0)
error ("iteration variable %qE should not be reduction",
DECL_NAME (decl));
- else if (simd == 1 && (n->value & GOVD_LASTPRIVATE) != 0)
+ else if (simd == 1 && (*n & GOVD_LASTPRIVATE) != 0)
error ("iteration variable %qE should not be lastprivate",
DECL_NAME (decl));
- else if (simd && (n->value & GOVD_PRIVATE) != 0)
+ else if (simd && (*n & GOVD_PRIVATE) != 0)
error ("iteration variable %qE should not be private",
DECL_NAME (decl));
- else if (simd == 2 && (n->value & GOVD_LINEAR) != 0)
+ else if (simd == 2 && (*n & GOVD_LINEAR) != 0)
error ("iteration variable %qE is predetermined linear",
DECL_NAME (decl));
}
@@ -6037,7 +6040,7 @@ omp_is_private (struct gimplify_omp_ctx *ctx, tree decl, int simd)
static bool
omp_check_private (struct gimplify_omp_ctx *ctx, tree decl, bool copyprivate)
{
- splay_tree_node n;
+ gimplify_tree_t::data_type *n;
do
{
@@ -6053,9 +6056,9 @@ omp_check_private (struct gimplify_omp_ctx *ctx, tree decl, bool copyprivate)
if ((ctx->region_type & (ORT_TARGET | ORT_TARGET_DATA)) != 0)
continue;
- n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+ n = ctx->variables->get(decl);
if (n != NULL)
- return (n->value & GOVD_SHARED) == 0;
+ return (*n & GOVD_SHARED) == 0;
}
while (ctx->region_type == ORT_WORKSHARE
|| ctx->region_type == ORT_SIMD);
@@ -6418,13 +6421,14 @@ struct gimplify_adjust_omp_clauses_data
remove PRIVATE, SHARED, and FIRSTPRIVATE clauses. */
static int
-gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
+gimplify_adjust_omp_clauses_1 (std::pair<tree, unsigned> n,
+ gimplify_adjust_omp_clauses_data *data)
{
tree *list_p = ((struct gimplify_adjust_omp_clauses_data *) data)->list_p;
gimple_seq *pre_p
= ((struct gimplify_adjust_omp_clauses_data *) data)->pre_p;
- tree decl = (tree) n->key;
- unsigned flags = n->value;
+ tree decl = n.first;
+ unsigned flags = n.second;
enum omp_clause_code code;
tree clause;
bool private_debug;
@@ -6455,9 +6459,8 @@ gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
struct gimplify_omp_ctx *ctx = gimplify_omp_ctxp->outer_context;
while (ctx != NULL)
{
- splay_tree_node on
- = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
- if (on && (on->value & (GOVD_FIRSTPRIVATE | GOVD_LASTPRIVATE
+ gimplify_tree_t::data_type *on = ctx->variables->get(decl);
+ if (on && (*on & (GOVD_FIRSTPRIVATE | GOVD_LASTPRIVATE
| GOVD_PRIVATE | GOVD_REDUCTION
| GOVD_LINEAR | GOVD_MAP)) != 0)
break;
@@ -6547,7 +6550,8 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree *list_p)
while ((c = *list_p) != NULL)
{
- splay_tree_node n;
+ gimplify_tree_t::data_type *n;
+
bool remove = false;
switch (OMP_CLAUSE_CODE (c))
@@ -6557,16 +6561,17 @@ 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);
- remove = !(n->value & GOVD_SEEN);
+ n = ctx->variables->get(decl);
+ gcc_assert(n);
+ remove = !(*n & GOVD_SEEN);
if (! remove)
{
bool shared = OMP_CLAUSE_CODE (c) == OMP_CLAUSE_SHARED;
- if ((n->value & GOVD_DEBUG_PRIVATE)
+ if ((*n & GOVD_DEBUG_PRIVATE)
|| lang_hooks.decls.omp_private_debug_clause (decl, shared))
{
- gcc_assert ((n->value & GOVD_DEBUG_PRIVATE) == 0
- || ((n->value & GOVD_DATA_SHARE_CLASS)
+ gcc_assert ((*n & GOVD_DEBUG_PRIVATE) == 0
+ || ((*n & GOVD_DATA_SHARE_CLASS)
== GOVD_PRIVATE));
OMP_CLAUSE_SET_CODE (c, OMP_CLAUSE_PRIVATE);
OMP_CLAUSE_PRIVATE_DEBUG (c) = 1;
@@ -6579,21 +6584,23 @@ 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,
- (splay_tree_key) decl);
- if (n == NULL
- || (n->value & GOVD_DATA_SHARE_CLASS) == 0)
+ gimplify_tree_t::data_type *n2;
+ gimplify_omp_ctx *octx = ctx->outer_context;
+ n2 = octx->variables->get(decl);
+ n = n2;
+ if (n2 == NULL
+ || (*n2 & GOVD_DATA_SHARE_CLASS) == 0)
{
int flags = GOVD_FIRSTPRIVATE;
/* #pragma omp distribute does not allow
lastprivate clause. */
if (!ctx->outer_context->distribute)
flags |= GOVD_LASTPRIVATE;
- if (n == NULL)
+ if (n2 == NULL)
omp_add_variable (ctx->outer_context, decl,
flags | GOVD_SEEN);
else
- n->value |= flags | GOVD_SEEN;
+ *n2 |= flags | GOVD_SEEN;
}
}
else if (!is_global_var (decl))
@@ -6606,38 +6613,37 @@ 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 = ctx->variables->get(decl);
+ gcc_assert(n);
OMP_CLAUSE_LASTPRIVATE_FIRSTPRIVATE (c)
- = (n->value & GOVD_FIRSTPRIVATE) != 0;
+ = (*n & GOVD_FIRSTPRIVATE) != 0;
break;
case OMP_CLAUSE_ALIGNED:
decl = OMP_CLAUSE_DECL (c);
if (!is_global_var (decl))
{
- n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
- remove = n == NULL || !(n->value & GOVD_SEEN);
+ n = ctx->variables->get(decl);
+ remove = n == NULL || !(*n & GOVD_SEEN);
if (!remove && TREE_CODE (TREE_TYPE (decl)) == POINTER_TYPE)
{
struct gimplify_omp_ctx *octx;
if (n != NULL
- && (n->value & (GOVD_DATA_SHARE_CLASS
- & ~GOVD_FIRSTPRIVATE)))
+ && (*n & (GOVD_DATA_SHARE_CLASS & ~GOVD_FIRSTPRIVATE)))
remove = true;
else
for (octx = ctx->outer_context; octx;
octx = octx->outer_context)
{
- n = splay_tree_lookup (octx->variables,
- (splay_tree_key) decl);
+ n = octx->variables->get(decl);
if (n == NULL)
continue;
- if (n->value & GOVD_LOCAL)
+ if (*n & GOVD_LOCAL)
break;
/* We have to avoid assigning a shared variable
to itself when trying to add
__builtin_assume_aligned. */
- if (n->value & GOVD_SHARED)
+ if (*n & GOVD_SHARED)
{
remove = true;
break;
@@ -6647,8 +6653,8 @@ 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);
- if (n != NULL && (n->value & GOVD_DATA_SHARE_CLASS) != 0)
+ n = ctx->variables->get(decl);
+ if (n != NULL && (*n & GOVD_DATA_SHARE_CLASS) != 0)
remove = true;
}
break;
@@ -6657,8 +6663,9 @@ 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);
- if (ctx->region_type == ORT_TARGET && !(n->value & GOVD_SEEN))
+ n = ctx->variables->get(decl);
+ gcc_assert(n);
+ if (ctx->region_type == ORT_TARGET && !(*n & GOVD_SEEN))
remove = true;
else if (DECL_SIZE (decl)
&& TREE_CODE (DECL_SIZE (decl)) != INTEGER_CST
@@ -6772,7 +6779,10 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree *list_p)
struct gimplify_adjust_omp_clauses_data data;
data.list_p = list_p;
data.pre_p = pre_p;
- splay_tree_foreach (ctx->variables, gimplify_adjust_omp_clauses_1, &data);
+ for (typename gimplify_tree_t::iterator it = ctx->variables->begin(),
+ ie = ctx->variables->end(); it != ie; ++it) {
+ gimplify_adjust_omp_clauses_1(*it, &data);
+ }
gimplify_omp_ctxp = ctx->outer_context;
delete_omp_context (ctx);
@@ -6986,12 +6996,11 @@ gimplify_omp_for (tree *expr_p, gimple_seq *pre_p)
/* Do this only on innermost construct for combined ones. */;
else if (simd)
{
- splay_tree_node n = splay_tree_lookup (gimplify_omp_ctxp->variables,
- (splay_tree_key)decl);
+ gimplify_tree_t::data_type *n = gimplify_omp_ctxp->variables->get(decl);
omp_is_private (gimplify_omp_ctxp, decl,
1 + (TREE_VEC_LENGTH (OMP_FOR_INIT (for_stmt))
!= 1));
- if (n != NULL && (n->value & GOVD_DATA_SHARE_CLASS) != 0)
+ if (n != NULL && (*n & GOVD_DATA_SHARE_CLASS) != 0)
omp_notice_variable (gimplify_omp_ctxp, decl, true);
else if (TREE_VEC_LENGTH (OMP_FOR_INIT (for_stmt)) == 1)
{
@@ -7020,10 +7029,9 @@ gimplify_omp_for (tree *expr_p, gimple_seq *pre_p)
{
struct gimplify_omp_ctx *outer
= gimplify_omp_ctxp->outer_context;
- n = splay_tree_lookup (outer->variables,
- (splay_tree_key) decl);
+ n = outer->variables->get(decl);
if (n != NULL
- && (n->value & GOVD_DATA_SHARE_CLASS) == GOVD_LOCAL)
+ && (*n & GOVD_DATA_SHARE_CLASS) == GOVD_LOCAL)
lastprivate = false;
else if (omp_check_private (outer, decl, false))
error ("lastprivate variable %qE is private in outer "
diff --git a/gcc/hash-map.h b/gcc/hash-map.h
index 4cca702..b668d88 100644
--- a/gcc/hash-map.h
+++ b/gcc/hash-map.h
@@ -187,6 +187,10 @@ class GTY((user)) hash_map
};
public:
+
+ typedef Key key_type;
+ typedef Value data_type;
+
explicit hash_map (size_t n = 13, bool ggc = false) : m_table (n, ggc) {}
/* Create a hash_map in ggc memory. */
[-- Attachment #2: splay.patch --]
[-- Type: application/octet-stream, Size: 21543 bytes --]
commit 3af9315e31e860628316211e56aa970b4eb36473
Author: hiraditya <hiraditya@gmail.com>
Date: Tue Mar 10 22:39:30 2015 -0500
Remove splay_tree from gimplify.c
diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index d822913..64e8d9d 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -92,6 +92,18 @@ along with GCC; see the file COPYING3. If not see
#include "tree-pass.h" /* FIXME: only for PROP_gimple_any */
#include "builtins.h"
+#include<map>
+
+/* A stable comparison functor to sort trees. */
+struct tree_compare_decl_uid {
+ bool operator ()(const tree &xa, const tree &xb) const
+ {
+ return DECL_UID (xa) < DECL_UID (xb);
+ }
+};
+
+typedef std::map<tree, unsigned, tree_compare_decl_uid> gimplify_tree_t;
+
enum gimplify_omp_var_data
{
GOVD_SEEN = 1,
@@ -166,7 +178,7 @@ struct gimplify_ctx
struct gimplify_omp_ctx
{
struct gimplify_omp_ctx *outer_context;
- splay_tree variables;
+ gimplify_tree_t *variables;
hash_set<tree> *privatized_types;
location_t location;
enum omp_clause_default_kind default_kind;
@@ -364,17 +376,6 @@ gimple_pop_condition (gimple_seq *pre_p)
}
}
-/* A stable comparison routine for use with splay trees and DECLs. */
-
-static int
-splay_tree_compare_decl_uid (splay_tree_key xa, splay_tree_key xb)
-{
- tree a = (tree) xa;
- tree b = (tree) xb;
-
- return DECL_UID (a) - DECL_UID (b);
-}
-
/* Create a new omp construct that deals with variable remapping. */
static struct gimplify_omp_ctx *
@@ -384,7 +385,7 @@ new_omp_context (enum omp_region_type region_type)
c = XCNEW (struct gimplify_omp_ctx);
c->outer_context = gimplify_omp_ctxp;
- c->variables = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
+ c->variables = new gimplify_tree_t;
c->privatized_types = new hash_set<tree>;
c->location = input_location;
c->region_type = region_type;
@@ -401,7 +402,7 @@ new_omp_context (enum omp_region_type region_type)
static void
delete_omp_context (struct gimplify_omp_ctx *c)
{
- splay_tree_delete (c->variables);
+ delete c->variables;
delete c->privatized_types;
XDELETE (c);
}
@@ -1093,8 +1094,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_key) t) == NULL))
+ || (ctx->variables->find(t) == ctx->variables->end())))
{
if (ctx->region_type == ORT_SIMD
&& TREE_ADDRESSABLE (t)
@@ -5522,20 +5522,21 @@ gimplify_stmt (tree *stmt_p, gimple_seq *seq_p)
void
omp_firstprivatize_variable (struct gimplify_omp_ctx *ctx, tree decl)
{
- splay_tree_node n;
+ gimplify_tree_t::iterator n;
if (decl == NULL || !DECL_P (decl))
return;
do
{
- n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
- if (n != NULL)
+ n = ctx->variables->find(decl);
+ if (n != ctx->variables->end())
{
- if (n->value & GOVD_SHARED)
- n->value = GOVD_FIRSTPRIVATE | (n->value & GOVD_SEEN);
- else if (n->value & GOVD_MAP)
- n->value |= GOVD_MAP_TO_ONLY;
+ unsigned &value = n->second;
+ if (value & GOVD_SHARED)
+ value = GOVD_FIRSTPRIVATE | (value & GOVD_SEEN);
+ else if (value & GOVD_MAP)
+ value |= GOVD_MAP_TO_ONLY;
else
return;
}
@@ -5612,7 +5613,7 @@ omp_firstprivatize_type_sizes (struct gimplify_omp_ctx *ctx, tree type)
static void
omp_add_variable (struct gimplify_omp_ctx *ctx, tree decl, unsigned int flags)
{
- splay_tree_node n;
+ gimplify_tree_t::iterator n;
unsigned int nflags;
tree t;
@@ -5625,19 +5626,20 @@ omp_add_variable (struct gimplify_omp_ctx *ctx, tree decl, unsigned int flags)
|| TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (decl)))
flags |= GOVD_SEEN;
- n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
- if (n != NULL && n->value != GOVD_ALIGNED)
+ n = ctx->variables->find(decl);
+ if (n != ctx->variables->end() && n->second != GOVD_ALIGNED)
{
+ unsigned &value = n->second;
/* We shouldn't be re-adding the decl with the same data
sharing class. */
- gcc_assert ((n->value & GOVD_DATA_SHARE_CLASS & flags) == 0);
+ gcc_assert ((value & GOVD_DATA_SHARE_CLASS & flags) == 0);
/* The only combination of data sharing classes we should see is
FIRSTPRIVATE and LASTPRIVATE. */
- nflags = n->value | flags;
+ nflags = value | flags;
gcc_assert ((nflags & GOVD_DATA_SHARE_CLASS)
== (GOVD_FIRSTPRIVATE | GOVD_LASTPRIVATE)
|| (flags & GOVD_DATA_SHARE_CLASS) == 0);
- n->value = nflags;
+ value = nflags;
return;
}
@@ -5705,10 +5707,10 @@ omp_add_variable (struct gimplify_omp_ctx *ctx, tree decl, unsigned int flags)
}
}
- if (n != NULL)
- n->value |= flags;
+ if (n != ctx->variables->end())
+ n->second |= flags;
else
- splay_tree_insert (ctx->variables, (splay_tree_key)decl, flags);
+ (*ctx->variables)[decl] = flags;
}
/* Notice a threadprivate variable DECL used in OMP context CTX.
@@ -5720,36 +5722,37 @@ static bool
omp_notice_threadprivate_variable (struct gimplify_omp_ctx *ctx, tree decl,
tree decl2)
{
- splay_tree_node n;
+ gimplify_tree_t::iterator n;
+
struct gimplify_omp_ctx *octx;
for (octx = ctx; octx; octx = octx->outer_context)
if (octx->region_type == ORT_TARGET)
{
- n = splay_tree_lookup (octx->variables, (splay_tree_key)decl);
- if (n == NULL)
+ n = octx->variables->find(decl);
+ if (n == octx->variables->end())
{
error ("threadprivate variable %qE used in target region",
DECL_NAME (decl));
error_at (octx->location, "enclosing target region");
- splay_tree_insert (octx->variables, (splay_tree_key)decl, 0);
+ (*octx->variables)[decl] = 0;
}
if (decl2)
- splay_tree_insert (octx->variables, (splay_tree_key)decl2, 0);
+ (*octx->variables)[decl2] = 0;
}
if (ctx->region_type != ORT_UNTIED_TASK)
return false;
- n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
- if (n == NULL)
+ n = ctx->variables->find(decl);
+ if (n == ctx->variables->end())
{
error ("threadprivate variable %qE used in untied task",
DECL_NAME (decl));
error_at (ctx->location, "enclosing task");
- splay_tree_insert (ctx->variables, (splay_tree_key)decl, 0);
+ (*ctx->variables)[decl] = 0;
}
if (decl2)
- splay_tree_insert (ctx->variables, (splay_tree_key)decl2, 0);
+ (*ctx->variables)[decl2] = 0;
return false;
}
@@ -5762,7 +5765,7 @@ omp_notice_threadprivate_variable (struct gimplify_omp_ctx *ctx, tree decl,
static bool
omp_notice_variable (struct gimplify_omp_ctx *ctx, tree decl, bool in_code)
{
- splay_tree_node n;
+ gimplify_tree_t::iterator n;
unsigned flags = in_code ? GOVD_SEEN : 0;
bool ret = false, shared;
@@ -5784,11 +5787,11 @@ omp_notice_variable (struct gimplify_omp_ctx *ctx, tree decl, bool in_code)
}
}
- n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
+ n = ctx->variables->find(decl);
if (ctx->region_type == ORT_TARGET)
{
ret = lang_hooks.decls.omp_disregard_value_expr (decl, true);
- if (n == NULL)
+ if (n == ctx->variables->end())
{
if (!lang_hooks.types.omp_mappable_type (TREE_TYPE (decl)))
{
@@ -5801,15 +5804,16 @@ omp_notice_variable (struct gimplify_omp_ctx *ctx, tree decl, bool in_code)
}
else
{
+ unsigned &value = n->second;
/* If nothing changed, there's nothing left to do. */
- if ((n->value & flags) == flags)
+ if ((value & flags) == flags)
return ret;
- n->value |= flags;
+ value |= flags;
}
goto do_outer;
}
- if (n == NULL)
+ if (n == ctx->variables->end())
{
enum omp_clause_default_kind default_kind, kind;
struct gimplify_omp_ctx *octx;
@@ -5867,12 +5871,12 @@ omp_notice_variable (struct gimplify_omp_ctx *ctx, tree decl, bool in_code)
omp_notice_variable (ctx->outer_context, decl, in_code);
for (octx = ctx->outer_context; octx; octx = octx->outer_context)
{
- splay_tree_node n2;
-
+ gimplify_tree_t::iterator n2;
if ((octx->region_type & (ORT_TARGET_DATA | ORT_TARGET)) != 0)
continue;
- n2 = splay_tree_lookup (octx->variables, (splay_tree_key) decl);
- if (n2 && (n2->value & GOVD_DATA_SHARE_CLASS) != GOVD_SHARED)
+ n2 = octx->variables->find(decl);
+ if (n2 != octx->variables->end() &&
+ (n2->second & GOVD_DATA_SHARE_CLASS) != GOVD_SHARED)
{
flags |= GOVD_FIRSTPRIVATE;
break;
@@ -5907,28 +5911,29 @@ omp_notice_variable (struct gimplify_omp_ctx *ctx, tree decl, bool in_code)
goto do_outer;
}
- if ((n->value & (GOVD_SEEN | GOVD_LOCAL)) == 0
+ if ((n->second & (GOVD_SEEN | GOVD_LOCAL)) == 0
&& (flags & (GOVD_SEEN | GOVD_LOCAL)) == GOVD_SEEN
&& DECL_SIZE (decl)
&& TREE_CODE (DECL_SIZE (decl)) != INTEGER_CST)
{
- splay_tree_node n2;
+ gimplify_tree_t::iterator n2;
tree t = DECL_VALUE_EXPR (decl);
gcc_assert (TREE_CODE (t) == INDIRECT_REF);
t = TREE_OPERAND (t, 0);
gcc_assert (DECL_P (t));
- n2 = splay_tree_lookup (ctx->variables, (splay_tree_key) t);
- n2->value |= GOVD_SEEN;
+ n2 = ctx->variables->find(t);
+ gcc_assert(n2 != ctx->variables->end());
+ n2->second |= GOVD_SEEN;
}
- shared = ((flags | n->value) & GOVD_SHARED) != 0;
+ shared = ((flags | n->second) & GOVD_SHARED) != 0;
ret = lang_hooks.decls.omp_disregard_value_expr (decl, shared);
/* If nothing changed, there's nothing left to do. */
- if ((n->value & flags) == flags)
+ if ((n->second & flags) == flags)
return ret;
- flags |= n->value;
- n->value = flags;
+ flags |= n->second;
+ n->second = flags;
do_outer:
/* If the variable is private in the current context, then we don't
@@ -5947,12 +5952,13 @@ omp_notice_variable (struct gimplify_omp_ctx *ctx, tree decl, bool in_code)
static bool
omp_is_private (struct gimplify_omp_ctx *ctx, tree decl, int simd)
{
- splay_tree_node n;
+ gimplify_tree_t::iterator n;
- n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
- if (n != NULL)
+ n = ctx->variables->find(decl);
+ if (n != ctx->variables->end())
{
- if (n->value & GOVD_SHARED)
+ unsigned &n_value = n->second;
+ if (n_value & GOVD_SHARED)
{
if (ctx == gimplify_omp_ctxp)
{
@@ -5962,30 +5968,30 @@ omp_is_private (struct gimplify_omp_ctx *ctx, tree decl, int simd)
else
error ("iteration variable %qE should be private",
DECL_NAME (decl));
- n->value = GOVD_PRIVATE;
+ n_value = GOVD_PRIVATE;
return true;
}
else
return false;
}
- else if ((n->value & GOVD_EXPLICIT) != 0
+ else if ((n_value & GOVD_EXPLICIT) != 0
&& (ctx == gimplify_omp_ctxp
|| (ctx->region_type == ORT_COMBINED_PARALLEL
&& gimplify_omp_ctxp->outer_context == ctx)))
{
- if ((n->value & GOVD_FIRSTPRIVATE) != 0)
+ if ((n_value & GOVD_FIRSTPRIVATE) != 0)
error ("iteration variable %qE should not be firstprivate",
DECL_NAME (decl));
- else if ((n->value & GOVD_REDUCTION) != 0)
+ else if ((n_value & GOVD_REDUCTION) != 0)
error ("iteration variable %qE should not be reduction",
DECL_NAME (decl));
- else if (simd == 1 && (n->value & GOVD_LASTPRIVATE) != 0)
+ else if (simd == 1 && (n_value & GOVD_LASTPRIVATE) != 0)
error ("iteration variable %qE should not be lastprivate",
DECL_NAME (decl));
- else if (simd && (n->value & GOVD_PRIVATE) != 0)
+ else if (simd && (n_value & GOVD_PRIVATE) != 0)
error ("iteration variable %qE should not be private",
DECL_NAME (decl));
- else if (simd == 2 && (n->value & GOVD_LINEAR) != 0)
+ else if (simd == 2 && (n_value & GOVD_LINEAR) != 0)
error ("iteration variable %qE is predetermined linear",
DECL_NAME (decl));
}
@@ -6009,7 +6015,7 @@ omp_is_private (struct gimplify_omp_ctx *ctx, tree decl, int simd)
static bool
omp_check_private (struct gimplify_omp_ctx *ctx, tree decl, bool copyprivate)
{
- splay_tree_node n;
+ gimplify_tree_t::iterator n;
do
{
@@ -6025,9 +6031,9 @@ omp_check_private (struct gimplify_omp_ctx *ctx, tree decl, bool copyprivate)
if ((ctx->region_type & (ORT_TARGET | ORT_TARGET_DATA)) != 0)
continue;
- n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
- if (n != NULL)
- return (n->value & GOVD_SHARED) == 0;
+ n = ctx->variables->find(decl);
+ if (n != ctx->variables->end())
+ return (n->second & GOVD_SHARED) == 0;
}
while (ctx->region_type == ORT_WORKSHARE
|| ctx->region_type == ORT_SIMD);
@@ -6390,13 +6396,14 @@ struct gimplify_adjust_omp_clauses_data
remove PRIVATE, SHARED, and FIRSTPRIVATE clauses. */
static int
-gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
+gimplify_adjust_omp_clauses_1 (std::pair<tree, unsigned> n,
+ gimplify_adjust_omp_clauses_data *data)
{
tree *list_p = ((struct gimplify_adjust_omp_clauses_data *) data)->list_p;
gimple_seq *pre_p
= ((struct gimplify_adjust_omp_clauses_data *) data)->pre_p;
- tree decl = (tree) n->key;
- unsigned flags = n->value;
+ tree decl = n.first;
+ unsigned flags = n.second;
enum omp_clause_code code;
tree clause;
bool private_debug;
@@ -6427,11 +6434,11 @@ gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
struct gimplify_omp_ctx *ctx = gimplify_omp_ctxp->outer_context;
while (ctx != NULL)
{
- splay_tree_node on
- = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
- if (on && (on->value & (GOVD_FIRSTPRIVATE | GOVD_LASTPRIVATE
- | GOVD_PRIVATE | GOVD_REDUCTION
- | GOVD_LINEAR | GOVD_MAP)) != 0)
+ gimplify_tree_t::iterator on = ctx->variables->find(decl);
+ if ((on != ctx->variables->end()) &&
+ (on->second & (GOVD_FIRSTPRIVATE | GOVD_LASTPRIVATE
+ | GOVD_PRIVATE | GOVD_REDUCTION
+ | GOVD_LINEAR | GOVD_MAP)) != 0)
break;
ctx = ctx->outer_context;
}
@@ -6519,7 +6526,8 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree *list_p)
while ((c = *list_p) != NULL)
{
- splay_tree_node n;
+ gimplify_tree_t::iterator n;
+
bool remove = false;
switch (OMP_CLAUSE_CODE (c))
@@ -6529,16 +6537,17 @@ 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);
- remove = !(n->value & GOVD_SEEN);
+ n = ctx->variables->find(decl);
+ gcc_assert(n != ctx->variables->end());
+ remove = !(n->second & GOVD_SEEN);
if (! remove)
{
bool shared = OMP_CLAUSE_CODE (c) == OMP_CLAUSE_SHARED;
- if ((n->value & GOVD_DEBUG_PRIVATE)
+ if ((n->second & GOVD_DEBUG_PRIVATE)
|| lang_hooks.decls.omp_private_debug_clause (decl, shared))
{
- gcc_assert ((n->value & GOVD_DEBUG_PRIVATE) == 0
- || ((n->value & GOVD_DATA_SHARE_CLASS)
+ gcc_assert ((n->second & GOVD_DEBUG_PRIVATE) == 0
+ || ((n->second & GOVD_DATA_SHARE_CLASS)
== GOVD_PRIVATE));
OMP_CLAUSE_SET_CODE (c, OMP_CLAUSE_PRIVATE);
OMP_CLAUSE_PRIVATE_DEBUG (c) = 1;
@@ -6550,22 +6559,23 @@ 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,
- (splay_tree_key) decl);
- if (n == NULL
- || (n->value & GOVD_DATA_SHARE_CLASS) == 0)
+ {
+ gimplify_tree_t::iterator n2;
+ gimplify_omp_ctx *octx = ctx->outer_context;
+ n2 = octx->variables->find(decl);
+ if (n2 == octx->variables->end()
+ || (n2->second & GOVD_DATA_SHARE_CLASS) == 0)
{
int flags = GOVD_FIRSTPRIVATE;
/* #pragma omp distribute does not allow
lastprivate clause. */
if (!ctx->outer_context->distribute)
flags |= GOVD_LASTPRIVATE;
- if (n == NULL)
+ if (n2 == octx->variables->end())
omp_add_variable (ctx->outer_context, decl,
flags | GOVD_SEEN);
else
- n->value |= flags | GOVD_SEEN;
+ n2->second |= flags | GOVD_SEEN;
}
}
else if (!is_global_var (decl))
@@ -6578,38 +6588,38 @@ 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 = ctx->variables->find(decl);
+ gcc_assert(n != ctx->variables->end());
OMP_CLAUSE_LASTPRIVATE_FIRSTPRIVATE (c)
- = (n->value & GOVD_FIRSTPRIVATE) != 0;
+ = (n->second & GOVD_FIRSTPRIVATE) != 0;
break;
case OMP_CLAUSE_ALIGNED:
decl = OMP_CLAUSE_DECL (c);
if (!is_global_var (decl))
{
- n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
- remove = n == NULL || !(n->value & GOVD_SEEN);
+ n = ctx->variables->find(decl);
+ remove = n == ctx->variables->end() || !(n->second & GOVD_SEEN);
if (!remove && TREE_CODE (TREE_TYPE (decl)) == POINTER_TYPE)
{
struct gimplify_omp_ctx *octx;
- if (n != NULL
- && (n->value & (GOVD_DATA_SHARE_CLASS
+ if (n != ctx->variables->end()
+ && (n->second & (GOVD_DATA_SHARE_CLASS
& ~GOVD_FIRSTPRIVATE)))
remove = true;
else
for (octx = ctx->outer_context; octx;
octx = octx->outer_context)
{
- n = splay_tree_lookup (octx->variables,
- (splay_tree_key) decl);
- if (n == NULL)
+ n = octx->variables->find(decl);
+ if (n == octx->variables->end())
continue;
- if (n->value & GOVD_LOCAL)
+ if (n->second & GOVD_LOCAL)
break;
/* We have to avoid assigning a shared variable
to itself when trying to add
__builtin_assume_aligned. */
- if (n->value & GOVD_SHARED)
+ if (n->second & GOVD_SHARED)
{
remove = true;
break;
@@ -6619,8 +6629,8 @@ 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);
- if (n != NULL && (n->value & GOVD_DATA_SHARE_CLASS) != 0)
+ n = ctx->variables->find(decl);
+ if (n != ctx->variables->end() && (n->second & GOVD_DATA_SHARE_CLASS) != 0)
remove = true;
}
break;
@@ -6629,8 +6639,9 @@ 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);
- if (ctx->region_type == ORT_TARGET && !(n->value & GOVD_SEEN))
+ n = ctx->variables->find(decl);
+ gcc_assert(n != ctx->variables->end());
+ if (ctx->region_type == ORT_TARGET && !(n->second & GOVD_SEEN))
remove = true;
else if (DECL_SIZE (decl)
&& TREE_CODE (DECL_SIZE (decl)) != INTEGER_CST
@@ -6744,7 +6755,10 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree *list_p)
struct gimplify_adjust_omp_clauses_data data;
data.list_p = list_p;
data.pre_p = pre_p;
- splay_tree_foreach (ctx->variables, gimplify_adjust_omp_clauses_1, &data);
+ for (typename gimplify_tree_t::iterator it = ctx->variables->begin(),
+ ie = ctx->variables->end(); it != ie; ++it) {
+ gimplify_adjust_omp_clauses_1(*it, &data);
+ }
gimplify_omp_ctxp = ctx->outer_context;
delete_omp_context (ctx);
@@ -6957,13 +6971,12 @@ gimplify_omp_for (tree *expr_p, gimple_seq *pre_p)
if (orig_for_stmt != for_stmt)
/* Do this only on innermost construct for combined ones. */;
else if (simd)
- {
- splay_tree_node n = splay_tree_lookup (gimplify_omp_ctxp->variables,
- (splay_tree_key)decl);
+ {
+ gimplify_tree_t::iterator n = gimplify_omp_ctxp->variables->find(decl);
omp_is_private (gimplify_omp_ctxp, decl,
1 + (TREE_VEC_LENGTH (OMP_FOR_INIT (for_stmt))
!= 1));
- if (n != NULL && (n->value & GOVD_DATA_SHARE_CLASS) != 0)
+ if (n != gimplify_omp_ctxp->variables->end() && (n->second & GOVD_DATA_SHARE_CLASS) != 0)
omp_notice_variable (gimplify_omp_ctxp, decl, true);
else if (TREE_VEC_LENGTH (OMP_FOR_INIT (for_stmt)) == 1)
{
@@ -6992,10 +7005,9 @@ gimplify_omp_for (tree *expr_p, gimple_seq *pre_p)
{
struct gimplify_omp_ctx *outer
= gimplify_omp_ctxp->outer_context;
- n = splay_tree_lookup (outer->variables,
- (splay_tree_key) decl);
- if (n != NULL
- && (n->value & GOVD_DATA_SHARE_CLASS) == GOVD_LOCAL)
+ n = outer->variables->find(decl);
+ if (n != outer->variables->end()
+ && (n->second & GOVD_DATA_SHARE_CLASS) == GOVD_LOCAL)
lastprivate = false;
else if (omp_check_private (outer, decl, false))
error ("lastprivate variable %qE is private in outer "
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Remove splay_tree from gimplify.c
2015-05-18 2:52 Remove splay_tree from gimplify.c Aditya K
@ 2015-05-27 16:59 ` Jeff Law
2015-05-27 17:06 ` Jakub Jelinek
0 siblings, 1 reply; 4+ messages in thread
From: Jeff Law @ 2015-05-27 16:59 UTC (permalink / raw)
To: Aditya K, gcc-patches, Jakub Jelinek
On 05/17/2015 06:23 PM, Aditya K wrote:
> 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.
>
> gcc/gimplify.c:1096: splay_tree_lookup (ctx->variables, (splay_tree_key) t) == NULL)
>
> Here, we change the tree itself `ctx'
> gcc/gimplify.c:5532: n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
>
>
> I think we don't need to update the tree in these cases at least.
>
> I have pasted the patch which removes splay_tree with hash_map. Another patch (attached) removes splay_tree with std::map.
> Please review the patches.
>
>
> Thanks,
> -Aditya
>
> gcc/ChangeLog:
>
> 2015-05-17 hiraditya <hiraditya@msn.com>
> Remove splay_tree from gimplify.c
>
> * gimplify.c (struct gimplify_omp_ctx): Replaced splay_tree with hash_map
> (splay_tree_compare_decl_uid): Likewise
> (new_omp_context): Likewise
> (delete_omp_context): Likewise
> (gimplify_bind_expr): Likewise
> (omp_firstprivatize_variable): Likewise
> (omp_add_variable): Likewise
> (omp_notice_threadprivate_variable): Likewise
> (omp_notice_variable): Likewise
> (omp_is_private): Likewise
> (omp_check_private): Likewise
> (gimplify_adjust_omp_clauses_1): Likewise
> (gimplify_adjust_omp_clauses): Likewise
> (gimplify_omp_for): Likewise
> * hash-map.h: Added typedefs.
So the question here is whether or not the other uses are commonly
looking up elements we've already searched for -- that's the whole
purpose of a splay tree, to improve lookup performance for commonly hit
items.
I believe most of this is Jakub's code, so he's probably in the best
position to comment on whether or not we're commonly looking up nodes
repeatedly in the tables. I don't think so at first glance, but I could
easily be wrong.
Aditya, have you done any benchmarking of this change? In theory, if
we're no longer doing the adjustments to the tree on lookups you should
be able to see/measure some kind of compile-time performance difference.
If it's too small to be measured, then one could argue there's really
no benefit in changing the implementation.
Given we've got a lot more hash_map usage than std::map, I'd suggest
going with hash_map if this patch moves forward -- if I had a better
feel for the data, access patterns, etc then I might make a suggestion
based on that, but I simply don't have that kind of insight on this code.
Jeff
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Remove splay_tree from gimplify.c
2015-05-27 16:59 ` Jeff Law
@ 2015-05-27 17:06 ` Jakub Jelinek
2015-05-27 19:54 ` Aditya K
0 siblings, 1 reply; 4+ messages in thread
From: Jakub Jelinek @ 2015-05-27 17:06 UTC (permalink / raw)
To: Jeff Law; +Cc: Aditya K, gcc-patches
On Wed, May 27, 2015 at 10:34:46AM -0600, Jeff Law wrote:
> So the question here is whether or not the other uses are commonly looking
> up elements we've already searched for -- that's the whole purpose of a
> splay tree, to improve lookup performance for commonly hit items.
First of all, this is only used for OpenMP/OpenACC/Cilk+ constructs,
so it really isn't that performance criticial.
The code probably dates back to Richard's and Diego's changes.
And, I believe splay trees are the right thing to use here, while sometimes
you lookup different vars, looking up the same var many times in a row is
very common.
Jakub
^ permalink raw reply [flat|nested] 4+ messages in thread
* RE: Remove splay_tree from gimplify.c
2015-05-27 17:06 ` Jakub Jelinek
@ 2015-05-27 19:54 ` Aditya K
0 siblings, 0 replies; 4+ messages in thread
From: Aditya K @ 2015-05-27 19:54 UTC (permalink / raw)
To: Jakub Jelinek, Jeff Law; +Cc: gcc-patches
----------------------------------------
> Date: Wed, 27 May 2015 18:41:55 +0200
> From: jakub@redhat.com
> To: law@redhat.com
> CC: hiraditya@msn.com; gcc-patches@gcc.gnu.org
> Subject: Re: Remove splay_tree from gimplify.c
>
> On Wed, May 27, 2015 at 10:34:46AM -0600, Jeff Law wrote:
>> So the question here is whether or not the other uses are commonly looking
>> up elements we've already searched for -- that's the whole purpose of a
>> splay tree, to improve lookup performance for commonly hit items.
>
> First of all, this is only used for OpenMP/OpenACC/Cilk+ constructs,
> so it really isn't that performance criticial.
> The code probably dates back to Richard's and Diego's changes.
> And, I believe splay trees are the right thing to use here, while sometimes
> you lookup different vars, looking up the same var many times in a row is
> very common.
If that is the case then I guess we can abandon the patch. I do not have a way to measure the compile time for OpenMP.
Thanks for the review.
-Aditya
>
> Jakub
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2015-05-27 18:59 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-05-18 2:52 Remove splay_tree from gimplify.c Aditya K
2015-05-27 16:59 ` Jeff Law
2015-05-27 17:06 ` Jakub Jelinek
2015-05-27 19:54 ` Aditya K
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).