* Proposal for adding splay_tree_find (to find elements without updating the nodes).
@ 2015-03-09 18:59 vax mzn
2015-03-09 19:26 ` Trevor Saunders
2015-03-09 23:00 ` Steven Bosscher
0 siblings, 2 replies; 26+ messages in thread
From: vax mzn @ 2015-03-09 18:59 UTC (permalink / raw)
To: gcc
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.
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.
-Aditya
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-09 18:59 Proposal for adding splay_tree_find (to find elements without updating the nodes) vax mzn
@ 2015-03-09 19:26 ` Trevor Saunders
2015-03-09 21:02 ` Aditya K
2015-03-09 23:00 ` Steven Bosscher
1 sibling, 1 reply; 26+ messages in thread
From: Trevor Saunders @ 2015-03-09 19:26 UTC (permalink / raw)
To: gcc
On Mon, Mar 09, 2015 at 06:59:10PM +0000, 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.
So, this makes sense, but I've always wondered if it wouldn't make more
sense to just use the red black tree in libstdc++ (or does it have a
splay tree of its own too?)
Trev
> 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.
>
>
> -Aditya
>
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-09 19:26 ` Trevor Saunders
@ 2015-03-09 21:02 ` Aditya K
0 siblings, 0 replies; 26+ messages in thread
From: Aditya K @ 2015-03-09 21:02 UTC (permalink / raw)
To: gcc
----------------------------------------
> Date: Mon, 9 Mar 2015 15:26:26 -0400
> From: tbsaunde@tbsaunde.org
> To: gcc@gcc.gnu.org
> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>
> On Mon, Mar 09, 2015 at 06:59:10PM +0000, 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.
>
> So, this makes sense, but I've always wondered if it wouldn't make more
> sense to just use the red black tree in libstdc++ (or does it have a
> splay tree of its own too?)
>
> Trev
>
Red-black trees do have better cost of balancing, although at a cost of higher complexity.
I'm not sure if using red-black trees would improve the performance because I don't have any data to back.
-Aditya
>> 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.
>>
>>
>> -Aditya
>>
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-09 18:59 Proposal for adding splay_tree_find (to find elements without updating the nodes) vax mzn
2015-03-09 19:26 ` Trevor Saunders
@ 2015-03-09 23:00 ` Steven Bosscher
2015-03-10 4:05 ` Aditya K
2015-03-10 10:20 ` Richard Biener
1 sibling, 2 replies; 26+ messages in thread
From: Steven Bosscher @ 2015-03-09 23:00 UTC (permalink / raw)
To: vax mzn; +Cc: gcc
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
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-09 23:00 ` Steven Bosscher
@ 2015-03-10 4:05 ` Aditya K
2015-03-10 10:20 ` Richard Biener
1 sibling, 0 replies; 26+ messages in thread
From: Aditya K @ 2015-03-10 4:05 UTC (permalink / raw)
To: Steven Bosscher, tbsaunde; +Cc: gcc
----------------------------------------
> From: stevenb.gcc@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: hiraditya@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 <hiraditya@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
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-09 23:00 ` Steven Bosscher
2015-03-10 4:05 ` Aditya K
@ 2015-03-10 10:20 ` Richard Biener
2015-03-13 18:51 ` Aditya K
1 sibling, 1 reply; 26+ messages in thread
From: Richard Biener @ 2015-03-10 10:20 UTC (permalink / raw)
To: Steven Bosscher; +Cc: vax mzn, gcc
On Mon, Mar 9, 2015 at 11:59 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> 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.
I agree with Steven here and wanted to say the same. If you don't
benefit from splay trees LRU scheme then use a different data structure.
Richard.
> Ciao!
> Steven
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-10 10:20 ` Richard Biener
@ 2015-03-13 18:51 ` Aditya K
2015-03-13 19:02 ` Jonathan Wakely
0 siblings, 1 reply; 26+ messages in thread
From: Aditya K @ 2015-03-13 18:51 UTC (permalink / raw)
To: Richard Biener, Steven Bosscher; +Cc: gcc
[-- Attachment #1: Type: text/plain, Size: 4429 bytes --]
---------------------------------------
> Date: Tue, 10 Mar 2015 11:20:07 +0100
> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> From: richard.guenther@gmail.com
> To: stevenb.gcc@gmail.com
> CC: hiraditya@msn.com; gcc@gcc.gnu.org
>
> On Mon, Mar 9, 2015 at 11:59 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
>> 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.
>
> I agree with Steven here and wanted to say the same. If you don't
> benefit from splay trees LRU scheme then use a different data structure.
>
> Richard.
>
>> Ciao!
>> Steven
Thanks Richard and Steven for the feedback. I tried to replace the use of splay tree with std::map, and got it to bootstrap.
The compile time on a few runs shows improvement but I wont trust those data because it is too good to be true.
Maybe, I dont have enough data points and this machine runs other things too.
1 Baseline: 1426175470 (SHA:7386c9d) Patch:1426258562 (SHA:592c06f)
2 Program | CC_Time CC_Real_Time CC_Time CC_Real_Time
3 MultiSource/Applications/ALAC/decode/alacconvert-decode | 4.2605 4.9840 2.6455 3.0826
4 MultiSource/Applications/ALAC/encode/alacconvert-encode | 4.3124 4.9600 2.7138 3.0725
5 MultiSource/Applications/Burg/burg | 5.6053 6.4204 3.5663 4.0837
6 MultiSource/Applications/JM/ldecod/ldecod | 33.3773 35.9444 20.7180 22.4260
7 MultiSource/Applications/JM/lencod/lencod | 74.2836 78.6588 47.3016 50.0484
8 MultiSource/Applications/SIBsim4/SIBsim4 | 5.5832 5.8932 3.0524 3.2456
9 MultiSource/Applications/SPASS/SPASS | 67.4992 72.1056 43.2258 45.7996
10 MultiSource/Applications/aha/aha | 0.5019 0.5894 0.3860 0.4406
11 MultiSource/Applications/d/make_dparser | 13.4930 14.5575 8.5084 9.2331
12 MultiSource/Applications/hbd/hbd | 4.7727 5.9225 2.9896 3.8366
13 MultiSource/Applications/hexxagon/hexxagon | 3.1735 3.6957 1.8297 2.2171
14 MultiSource/Applications/kimwitu++/kc | 29.6117 31.8364 18.0744 19.5862
15 MultiSource/Applications/lambda-0.1.3/lambda | 4.5274 4.9125 2.7136 2.9241
I have attached my patch. Please give feedback/suggestions for improvement.
Thanks
-Aditya
[-- Attachment #2: splay.patch --]
[-- Type: application/octet-stream, Size: 21942 bytes --]
commit 592c06f00c1c1751a7aac50cf5cc7e218fe7c3c3
Author: Aditya Kumar <aditya.k6@samsung.com>
Date: Wed Mar 11 09:45:07 2015 -0500
Remove splay tree from gimplify.c
diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index d822913..4688544 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -92,6 +92,19 @@ 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 compare_variables {
+ bool operator ()(const tree &xa, const tree &xb) const
+ {
+ return DECL_UID (xa) - DECL_UID (xb);
+ }
+};
+
+typedef std::map<tree, unsigned, compare_variables> gimplify_tree_t;
+
enum gimplify_omp_var_data
{
GOVD_SEEN = 1,
@@ -166,7 +179,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 +377,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 +386,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 = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
c->privatized_types = new hash_set<tree>;
c->location = input_location;
c->region_type = region_type;
@@ -398,14 +400,6 @@ new_omp_context (enum omp_region_type region_type)
/* Destroy an omp construct that deals with variable remapping. */
-static void
-delete_omp_context (struct gimplify_omp_ctx *c)
-{
- splay_tree_delete (c->variables);
- delete c->privatized_types;
- XDELETE (c);
-}
-
static void omp_add_variable (struct gimplify_omp_ctx *, tree, unsigned int);
static bool omp_notice_variable (struct gimplify_omp_ctx *, tree, bool);
@@ -1093,8 +1087,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 +5515,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 +5606,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 +5619,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 +5700,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 +5715,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 +5758,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 +5780,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 +5797,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 +5864,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 +5904,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 +5945,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 +5961,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 +6008,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 +6024,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 +6389,13 @@ 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, void *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 +6426,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 +6518,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 +6529,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 +6551,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 +6580,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 +6621,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 +6631,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,10 +6747,12 @@ 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);
}
/* Gimplify OACC_CACHE. */
@@ -6957,13 +6962,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 +6996,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 "
@@ -9105,7 +9108,6 @@ gimplify_body (tree fndecl, bool do_parms)
if ((flag_openacc || flag_openmp || flag_openmp_simd)
&& gimplify_omp_ctxp)
{
- delete_omp_context (gimplify_omp_ctxp);
gimplify_omp_ctxp = NULL;
}
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-13 18:51 ` Aditya K
@ 2015-03-13 19:02 ` Jonathan Wakely
2015-03-13 19:32 ` Aditya K
0 siblings, 1 reply; 26+ messages in thread
From: Jonathan Wakely @ 2015-03-13 19:02 UTC (permalink / raw)
To: Aditya K; +Cc: Richard Biener, Steven Bosscher, gcc
Are you sure your compare_variables functor is correct?
Subtracting the two values seems very strange for a strict weak ordering.
(Also "compare_variables" is a pretty poor name!)
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-13 19:02 ` Jonathan Wakely
@ 2015-03-13 19:32 ` Aditya K
2015-03-15 6:33 ` Trevor Saunders
0 siblings, 1 reply; 26+ messages in thread
From: Aditya K @ 2015-03-13 19:32 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: Richard Biener, Steven Bosscher, gcc
[-- Attachment #1: Type: text/plain, Size: 808 bytes --]
You're right. I'll change this to:
/* 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);
}
};
New patch attached.
Thanks,
-Aditya
----------------------------------------
> Date: Fri, 13 Mar 2015 19:02:11 +0000
> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> From: jwakely.gcc@gmail.com
> To: hiraditya@msn.com
> CC: richard.guenther@gmail.com; stevenb.gcc@gmail.com; gcc@gcc.gnu.org
>
> Are you sure your compare_variables functor is correct?
>
> Subtracting the two values seems very strange for a strict weak ordering.
>
> (Also "compare_variables" is a pretty poor name!)
[-- Attachment #2: splay.patch --]
[-- Type: application/octet-stream, Size: 21950 bytes --]
commit 592c06f00c1c1751a7aac50cf5cc7e218fe7c3c3
Author: Aditya Kumar <aditya.k6@samsung.com>
Date: Wed Mar 11 09:45:07 2015 -0500
Remove splay tree from gimplify.c
diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index d822913..4688544 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -92,6 +92,19 @@ 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 +179,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 +377,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 +386,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 = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
c->privatized_types = new hash_set<tree>;
c->location = input_location;
c->region_type = region_type;
@@ -398,14 +400,6 @@ new_omp_context (enum omp_region_type region_type)
/* Destroy an omp construct that deals with variable remapping. */
-static void
-delete_omp_context (struct gimplify_omp_ctx *c)
-{
- splay_tree_delete (c->variables);
- delete c->privatized_types;
- XDELETE (c);
-}
-
static void omp_add_variable (struct gimplify_omp_ctx *, tree, unsigned int);
static bool omp_notice_variable (struct gimplify_omp_ctx *, tree, bool);
@@ -1093,8 +1087,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 +5515,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 +5606,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 +5619,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 +5700,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 +5715,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 +5758,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 +5780,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 +5797,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 +5864,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 +5904,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 +5945,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 +5961,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 +6008,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 +6024,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 +6389,13 @@ 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, void *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 +6426,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 +6518,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 +6529,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 +6551,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 +6580,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 +6621,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 +6631,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,10 +6747,12 @@ 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);
}
/* Gimplify OACC_CACHE. */
@@ -6957,13 +6962,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 +6996,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 "
@@ -9105,7 +9108,6 @@ gimplify_body (tree fndecl, bool do_parms)
if ((flag_openacc || flag_openmp || flag_openmp_simd)
&& gimplify_omp_ctxp)
{
- delete_omp_context (gimplify_omp_ctxp);
gimplify_omp_ctxp = NULL;
}
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-13 19:32 ` Aditya K
@ 2015-03-15 6:33 ` Trevor Saunders
2015-03-16 3:33 ` Aditya K
0 siblings, 1 reply; 26+ messages in thread
From: Trevor Saunders @ 2015-03-15 6:33 UTC (permalink / raw)
To: gcc
hi,
I'm only commenting on algorithmic stuff at this point, you should make
sure this doesn't regress anything in make check. This stuff only
effects code using omp stuff so compiling random c++ is unlikely to test
this code at all.
Also please follow the style in
https://gcc.gnu.org/codingconventions.html
and usually try to make new code similar to what's around it.
@@ -384,7 +386,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 = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
I don't think this is what you want, xcnew is a calloc wrapper and
doesn't call the ctor for gimplify_omp_ctx. For now placement new is
probably the simplest way to get what you want.
-static void
-delete_omp_context (struct gimplify_omp_ctx *c)
-{
- splay_tree_delete (c->variables);
- delete c->privatized_types;
- XDELETE (c);
-}
hm, why?
-gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
+gimplify_adjust_omp_clauses_1 (std::pair<tree, unsigned> n, void *data)
You can now change the type of data from void * to const
gimplify_adjust_omp_clauses_data *
thanks!
Trev
On Fri, Mar 13, 2015 at 07:32:03PM +0000, Aditya K wrote:
> You're right. I'll change this to:
>
> /* 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);
> Â }
> };
>
> New patch attached.
>
>
> Thanks,
> -Aditya
>
>
> ----------------------------------------
> > Date: Fri, 13 Mar 2015 19:02:11 +0000
> > Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> > From: jwakely.gcc@gmail.com
> > To: hiraditya@msn.com
> > CC: richard.guenther@gmail.com; stevenb.gcc@gmail.com; gcc@gcc.gnu.org
> >
> > Are you sure your compare_variables functor is correct?
> >
> > Subtracting the two values seems very strange for a strict weak ordering.
> >
> > (Also "compare_variables" is a pretty poor name!)
>
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-15 6:33 ` Trevor Saunders
@ 2015-03-16 3:33 ` Aditya K
2015-03-16 4:17 ` Trevor Saunders
2015-03-18 10:50 ` Richard Biener
0 siblings, 2 replies; 26+ messages in thread
From: Aditya K @ 2015-03-16 3:33 UTC (permalink / raw)
To: Trevor Saunders, gcc
[-- Attachment #1: Type: text/plain, Size: 3165 bytes --]
----------------------------------------
> Date: Sun, 15 Mar 2015 02:32:23 -0400
> From: tbsaunde@tbsaunde.org
> To: gcc@gcc.gnu.org
> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>
> hi,
>
> I'm only commenting on algorithmic stuff at this point, you should make
> sure this doesn't regress anything in make check. This stuff only
> effects code using omp stuff so compiling random c++ is unlikely to test
> this code at all.
>
> Also please follow the style in
> https://gcc.gnu.org/codingconventions.html
> and usually try to make new code similar to what's around it.
>
> @@ -384,7 +386,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 = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
>
> I don't think this is what you want, xcnew is a calloc wrapper and
> doesn't call the ctor for gimplify_omp_ctx. For now placement new is
> probably the simplest way to get what you want.
>
Thanks for pointing this out. I'll do it the way c->privatized_types has been allocated.
e.g., by making c->variables a pointer to std::map and c->variables = new gimplify_tree_t;
> -static void
> -delete_omp_context (struct gimplify_omp_ctx *c)
> -{
> - splay_tree_delete (c->variables);
> - delete c->privatized_types;
> - XDELETE (c);
> -}
>
> hm, why?
>
My bad, I'll restore this.
> -gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
> +gimplify_adjust_omp_clauses_1 (std::pair<tree, unsigned> n, void *data)
>
> You can now change the type of data from void * to const
> gimplify_adjust_omp_clauses_data *
Done!
Thanks for the feedback, they were really helpful. I have updated the patch. Please review this.
Also, although I run `make check` while compiling gcc (with bootstrap enabled), I'm not sure if 'omp' related tests were exercised.
I'm still unfamiliar with several components of gcc. Any pointers on how to ensure all tests were run, would be useful.
-Aditya
>
> thanks!
>
> Trev
>
> On Fri, Mar 13, 2015 at 07:32:03PM +0000, Aditya K wrote:
>> You're right. I'll change this to:
>>
>> /* 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);
>> }
>> };
>>
>> New patch attached.
>>
>>
>> Thanks,
>> -Aditya
>>
>>
>> ----------------------------------------
>>> Date: Fri, 13 Mar 2015 19:02:11 +0000
>>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>> From: jwakely.gcc@gmail.com
>>> To: hiraditya@msn.com
>>> CC: richard.guenther@gmail.com; stevenb.gcc@gmail.com; gcc@gcc.gnu.org
>>>
>>> Are you sure your compare_variables functor is correct?
>>>
>>> Subtracting the two values seems very strange for a strict weak ordering.
>>>
>>> (Also "compare_variables" is a pretty poor name!)
>>
>
>
[-- 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] 26+ messages in thread
* Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-16 3:33 ` Aditya K
@ 2015-03-16 4:17 ` Trevor Saunders
2015-03-18 10:50 ` Richard Biener
1 sibling, 0 replies; 26+ messages in thread
From: Trevor Saunders @ 2015-03-16 4:17 UTC (permalink / raw)
To: gcc
On Mon, Mar 16, 2015 at 03:33:18AM +0000, Aditya K wrote:
>
>
> ----------------------------------------
> > Date: Sun, 15 Mar 2015 02:32:23 -0400
> > From: tbsaunde@tbsaunde.org
> > To: gcc@gcc.gnu.org
> > Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> >
> > hi,
> >
> > I'm only commenting on algorithmic stuff at this point, you should make
> > sure this doesn't regress anything in make check. This stuff only
> > effects code using omp stuff so compiling random c++ is unlikely to test
> > this code at all.
> >
> > Also please follow the style in
> > https://gcc.gnu.org/codingconventions.html
> > and usually try to make new code similar to what's around it.
> >
> > @@ -384,7 +386,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 = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
> >
> > I don't think this is what you want, xcnew is a calloc wrapper and
> > doesn't call the ctor for gimplify_omp_ctx. For now placement new is
> > probably the simplest way to get what you want.
> >
> Thanks for pointing this out. I'll do it the way c->privatized_types has been allocated.
> e.g., by making c->variables a pointer to std::map and  c->variables = new gimplify_tree_t;
that works too, though I'd be a more descriptive name than
gimplify_tree_t, maybe omp_variables_map?
>
>
> > -static void
> > -delete_omp_context (struct gimplify_omp_ctx *c)
> > -{
> > - splay_tree_delete (c->variables);
> > - delete c->privatized_types;
> > - XDELETE (c);
> > -}
> >
> > hm, why?
> >
> My bad, I'll restore this.
>
> > -gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
> > +gimplify_adjust_omp_clauses_1 (std::pair<tree, unsigned> n, void *data)
> >
> > You can now change the type of data from void * to const
> > gimplify_adjust_omp_clauses_data *
>
> Done!
>
>
> Thanks for the feedback, they were really helpful. I have updated the patch. Please review this.
> Also, although I run `make check` while compiling gcc (with bootstrap enabled), I'm not sure if 'omp' related tests were exercised.
> I'm still unfamiliar with several components of gcc. Any pointers on how to ensure all tests were run, would be useful.
https://gcc.gnu.org/install/test.html should help, though unfortunately
you'll probably find the easiest way to check for regressions is to do
one run of straight trunk, then another with your patch. Saddly a bunch
of people have own scripts to deal with administrivia, but there isn't a
standardized way that's simple.
Trev
>
>
> -Aditya
>
>
>
>
> >
> > thanks!
> >
> > Trev
> >
> > On Fri, Mar 13, 2015 at 07:32:03PM +0000, Aditya K wrote:
> >> You're right. I'll change this to:
> >>
> >> /* 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);
> >> }
> >> };
> >>
> >> New patch attached.
> >>
> >>
> >> Thanks,
> >> -Aditya
> >>
> >>
> >> ----------------------------------------
> >>> Date: Fri, 13 Mar 2015 19:02:11 +0000
> >>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> >>> From: jwakely.gcc@gmail.com
> >>> To: hiraditya@msn.com
> >>> CC: richard.guenther@gmail.com; stevenb.gcc@gmail.com; gcc@gcc.gnu.org
> >>>
> >>> Are you sure your compare_variables functor is correct?
> >>>
> >>> Subtracting the two values seems very strange for a strict weak ordering.
> >>>
> >>> (Also "compare_variables" is a pretty poor name!)
> >>
> >
> >
>
>
>
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-16 3:33 ` Aditya K
2015-03-16 4:17 ` Trevor Saunders
@ 2015-03-18 10:50 ` Richard Biener
2015-03-18 15:50 ` Aditya K
1 sibling, 1 reply; 26+ messages in thread
From: Richard Biener @ 2015-03-18 10:50 UTC (permalink / raw)
To: Aditya K; +Cc: Trevor Saunders, gcc
On Mon, Mar 16, 2015 at 4:33 AM, Aditya K <hiraditya@msn.com> wrote:
>
>
> ----------------------------------------
>> Date: Sun, 15 Mar 2015 02:32:23 -0400
>> From: tbsaunde@tbsaunde.org
>> To: gcc@gcc.gnu.org
>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>
>> hi,
>>
>> I'm only commenting on algorithmic stuff at this point, you should make
>> sure this doesn't regress anything in make check. This stuff only
>> effects code using omp stuff so compiling random c++ is unlikely to test
>> this code at all.
>>
>> Also please follow the style in
>> https://gcc.gnu.org/codingconventions.html
>> and usually try to make new code similar to what's around it.
>>
>> @@ -384,7 +386,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 = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
>>
>> I don't think this is what you want, xcnew is a calloc wrapper and
>> doesn't call the ctor for gimplify_omp_ctx. For now placement new is
>> probably the simplest way to get what you want.
>>
> Thanks for pointing this out. I'll do it the way c->privatized_types has been allocated.
> e.g., by making c->variables a pointer to std::map and c->variables = new gimplify_tree_t;
>
>
>> -static void
>> -delete_omp_context (struct gimplify_omp_ctx *c)
>> -{
>> - splay_tree_delete (c->variables);
>> - delete c->privatized_types;
>> - XDELETE (c);
>> -}
>>
>> hm, why?
>>
> My bad, I'll restore this.
>
>> -gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
>> +gimplify_adjust_omp_clauses_1 (std::pair<tree, unsigned> n, void *data)
>>
>> You can now change the type of data from void * to const
>> gimplify_adjust_omp_clauses_data *
>
> Done!
>
>
> Thanks for the feedback, they were really helpful. I have updated the patch. Please review this.
> Also, although I run `make check` while compiling gcc (with bootstrap enabled), I'm not sure if 'omp' related tests were exercised.
> I'm still unfamiliar with several components of gcc. Any pointers on how to ensure all tests were run, would be useful.
I'm not sure we want to use std::map. Can you use GCCs own hash_map
here?
Richard.
>
> -Aditya
>
>
>
>
>>
>> thanks!
>>
>> Trev
>>
>> On Fri, Mar 13, 2015 at 07:32:03PM +0000, Aditya K wrote:
>>> You're right. I'll change this to:
>>>
>>> /* 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);
>>> }
>>> };
>>>
>>> New patch attached.
>>>
>>>
>>> Thanks,
>>> -Aditya
>>>
>>>
>>> ----------------------------------------
>>>> Date: Fri, 13 Mar 2015 19:02:11 +0000
>>>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>>> From: jwakely.gcc@gmail.com
>>>> To: hiraditya@msn.com
>>>> CC: richard.guenther@gmail.com; stevenb.gcc@gmail.com; gcc@gcc.gnu.org
>>>>
>>>> Are you sure your compare_variables functor is correct?
>>>>
>>>> Subtracting the two values seems very strange for a strict weak ordering.
>>>>
>>>> (Also "compare_variables" is a pretty poor name!)
>>>
>>
>>
>
>
>
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-18 10:50 ` Richard Biener
@ 2015-03-18 15:50 ` Aditya K
2015-03-18 16:31 ` Prathamesh Kulkarni
0 siblings, 1 reply; 26+ messages in thread
From: Aditya K @ 2015-03-18 15:50 UTC (permalink / raw)
To: Richard Biener; +Cc: Trevor Saunders, gcc
----------------------------------------
> Date: Wed, 18 Mar 2015 11:50:16 +0100
> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> From: richard.guenther@gmail.com
> To: hiraditya@msn.com
> CC: tbsaunde@tbsaunde.org; gcc@gcc.gnu.org
>
> On Mon, Mar 16, 2015 at 4:33 AM, Aditya K <hiraditya@msn.com> wrote:
>>
>>
>> ----------------------------------------
>>> Date: Sun, 15 Mar 2015 02:32:23 -0400
>>> From: tbsaunde@tbsaunde.org
>>> To: gcc@gcc.gnu.org
>>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>>
>>> hi,
>>>
>>> I'm only commenting on algorithmic stuff at this point, you should make
>>> sure this doesn't regress anything in make check. This stuff only
>>> effects code using omp stuff so compiling random c++ is unlikely to test
>>> this code at all.
>>>
>>> Also please follow the style in
>>> https://gcc.gnu.org/codingconventions.html
>>> and usually try to make new code similar to what's around it.
>>>
>>> @@ -384,7 +386,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 = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
>>>
>>> I don't think this is what you want, xcnew is a calloc wrapper and
>>> doesn't call the ctor for gimplify_omp_ctx. For now placement new is
>>> probably the simplest way to get what you want.
>>>
>> Thanks for pointing this out. I'll do it the way c->privatized_types has been allocated.
>> e.g., by making c->variables a pointer to std::map and c->variables = new gimplify_tree_t;
>>
>>
>>> -static void
>>> -delete_omp_context (struct gimplify_omp_ctx *c)
>>> -{
>>> - splay_tree_delete (c->variables);
>>> - delete c->privatized_types;
>>> - XDELETE (c);
>>> -}
>>>
>>> hm, why?
>>>
>> My bad, I'll restore this.
>>
>>> -gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
>>> +gimplify_adjust_omp_clauses_1 (std::pair<tree, unsigned> n, void *data)
>>>
>>> You can now change the type of data from void * to const
>>> gimplify_adjust_omp_clauses_data *
>>
>> Done!
>>
>>
>> Thanks for the feedback, they were really helpful. I have updated the patch. Please review this.
>> Also, although I run `make check` while compiling gcc (with bootstrap enabled), I'm not sure if 'omp' related tests were exercised.
>> I'm still unfamiliar with several components of gcc. Any pointers on how to ensure all tests were run, would be useful.
>
> I'm not sure we want to use std::map. Can you use GCCs own hash_map
> here?
Ok, I'll try to use has_map. I was under the impression that we can use standard library features, that's why I used std::map.
Thanks,
-Aditya
>
> Richard.
>
>>
>> -Aditya
>>
>>
>>
>>
>>>
>>> thanks!
>>>
>>> Trev
>>>
>>> On Fri, Mar 13, 2015 at 07:32:03PM +0000, Aditya K wrote:
>>>> You're right. I'll change this to:
>>>>
>>>> /* 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);
>>>> }
>>>> };
>>>>
>>>> New patch attached.
>>>>
>>>>
>>>> Thanks,
>>>> -Aditya
>>>>
>>>>
>>>> ----------------------------------------
>>>>> Date: Fri, 13 Mar 2015 19:02:11 +0000
>>>>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>>>> From: jwakely.gcc@gmail.com
>>>>> To: hiraditya@msn.com
>>>>> CC: richard.guenther@gmail.com; stevenb.gcc@gmail.com; gcc@gcc.gnu.org
>>>>>
>>>>> Are you sure your compare_variables functor is correct?
>>>>>
>>>>> Subtracting the two values seems very strange for a strict weak ordering.
>>>>>
>>>>> (Also "compare_variables" is a pretty poor name!)
>>>>
>>>
>>>
>>
>>
>>
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-18 15:50 ` Aditya K
@ 2015-03-18 16:31 ` Prathamesh Kulkarni
2015-03-18 18:14 ` Aditya K
0 siblings, 1 reply; 26+ messages in thread
From: Prathamesh Kulkarni @ 2015-03-18 16:31 UTC (permalink / raw)
To: Aditya K; +Cc: Richard Biener, Trevor Saunders, gcc
On 18 March 2015 at 21:20, Aditya K <hiraditya@msn.com> wrote:
>
>
> ----------------------------------------
>> Date: Wed, 18 Mar 2015 11:50:16 +0100
>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>> From: richard.guenther@gmail.com
>> To: hiraditya@msn.com
>> CC: tbsaunde@tbsaunde.org; gcc@gcc.gnu.org
>>
>> On Mon, Mar 16, 2015 at 4:33 AM, Aditya K <hiraditya@msn.com> wrote:
>>>
>>>
>>> ----------------------------------------
>>>> Date: Sun, 15 Mar 2015 02:32:23 -0400
>>>> From: tbsaunde@tbsaunde.org
>>>> To: gcc@gcc.gnu.org
>>>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>>>
>>>> hi,
>>>>
>>>> I'm only commenting on algorithmic stuff at this point, you should make
>>>> sure this doesn't regress anything in make check. This stuff only
>>>> effects code using omp stuff so compiling random c++ is unlikely to test
>>>> this code at all.
>>>>
>>>> Also please follow the style in
>>>> https://gcc.gnu.org/codingconventions.html
>>>> and usually try to make new code similar to what's around it.
>>>>
>>>> @@ -384,7 +386,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 = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
>>>>
>>>> I don't think this is what you want, xcnew is a calloc wrapper and
>>>> doesn't call the ctor for gimplify_omp_ctx. For now placement new is
>>>> probably the simplest way to get what you want.
>>>>
>>> Thanks for pointing this out. I'll do it the way c->privatized_types has been allocated.
>>> e.g., by making c->variables a pointer to std::map and c->variables = new gimplify_tree_t;
>>>
>>>
>>>> -static void
>>>> -delete_omp_context (struct gimplify_omp_ctx *c)
>>>> -{
>>>> - splay_tree_delete (c->variables);
>>>> - delete c->privatized_types;
>>>> - XDELETE (c);
>>>> -}
>>>>
>>>> hm, why?
>>>>
>>> My bad, I'll restore this.
>>>
>>>> -gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
>>>> +gimplify_adjust_omp_clauses_1 (std::pair<tree, unsigned> n, void *data)
>>>>
>>>> You can now change the type of data from void * to const
>>>> gimplify_adjust_omp_clauses_data *
>>>
>>> Done!
>>>
>>>
>>> Thanks for the feedback, they were really helpful. I have updated the patch. Please review this.
>>> Also, although I run `make check` while compiling gcc (with bootstrap enabled), I'm not sure if 'omp' related tests were exercised.
>>> I'm still unfamiliar with several components of gcc. Any pointers on how to ensure all tests were run, would be useful.
>>
>> I'm not sure we want to use std::map. Can you use GCCs own hash_map
>> here?
>
> Ok, I'll try to use has_map. I was under the impression that we can use standard library features, that's why I used std::map.
>
Using std::map caused a bootstrap build problem on AIX.
see: https://gcc.gnu.org/ml/gcc-patches/2014-10/msg02608.html
However I am not sure if that's true any more after the following fix
was commmited:
https://gcc.gnu.org/ml/libstdc++/2014-10/msg00195.html
Regards,
Prathamesh
> Thanks,
> -Aditya
>
>>
>> Richard.
>>
>>>
>>> -Aditya
>>>
>>>
>>>
>>>
>>>>
>>>> thanks!
>>>>
>>>> Trev
>>>>
>>>> On Fri, Mar 13, 2015 at 07:32:03PM +0000, Aditya K wrote:
>>>>> You're right. I'll change this to:
>>>>>
>>>>> /* 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);
>>>>> }
>>>>> };
>>>>>
>>>>> New patch attached.
>>>>>
>>>>>
>>>>> Thanks,
>>>>> -Aditya
>>>>>
>>>>>
>>>>> ----------------------------------------
>>>>>> Date: Fri, 13 Mar 2015 19:02:11 +0000
>>>>>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>>>>> From: jwakely.gcc@gmail.com
>>>>>> To: hiraditya@msn.com
>>>>>> CC: richard.guenther@gmail.com; stevenb.gcc@gmail.com; gcc@gcc.gnu.org
>>>>>>
>>>>>> Are you sure your compare_variables functor is correct?
>>>>>>
>>>>>> Subtracting the two values seems very strange for a strict weak ordering.
>>>>>>
>>>>>> (Also "compare_variables" is a pretty poor name!)
>>>>>
>>>>
>>>>
>>>
>>>
>>>
>
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-18 16:31 ` Prathamesh Kulkarni
@ 2015-03-18 18:14 ` Aditya K
2015-03-30 22:28 ` Aditya K
0 siblings, 1 reply; 26+ messages in thread
From: Aditya K @ 2015-03-18 18:14 UTC (permalink / raw)
To: Prathamesh Kulkarni; +Cc: Richard Biener, Trevor Saunders, gcc
----------------------------------------
> Date: Wed, 18 Mar 2015 22:01:18 +0530
> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> From: prathamesh.kulkarni@linaro.org
> To: hiraditya@msn.com
> CC: richard.guenther@gmail.com; tbsaunde@tbsaunde.org; gcc@gcc.gnu.org
>
> On 18 March 2015 at 21:20, Aditya K <hiraditya@msn.com> wrote:
>>
>>
>> ----------------------------------------
>>> Date: Wed, 18 Mar 2015 11:50:16 +0100
>>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>> From: richard.guenther@gmail.com
>>> To: hiraditya@msn.com
>>> CC: tbsaunde@tbsaunde.org; gcc@gcc.gnu.org
>>>
>>> On Mon, Mar 16, 2015 at 4:33 AM, Aditya K <hiraditya@msn.com> wrote:
>>>>
>>>>
>>>> ----------------------------------------
>>>>> Date: Sun, 15 Mar 2015 02:32:23 -0400
>>>>> From: tbsaunde@tbsaunde.org
>>>>> To: gcc@gcc.gnu.org
>>>>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>>>>
>>>>> hi,
>>>>>
>>>>> I'm only commenting on algorithmic stuff at this point, you should make
>>>>> sure this doesn't regress anything in make check. This stuff only
>>>>> effects code using omp stuff so compiling random c++ is unlikely to test
>>>>> this code at all.
>>>>>
>>>>> Also please follow the style in
>>>>> https://gcc.gnu.org/codingconventions.html
>>>>> and usually try to make new code similar to what's around it.
>>>>>
>>>>> @@ -384,7 +386,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 = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
>>>>>
>>>>> I don't think this is what you want, xcnew is a calloc wrapper and
>>>>> doesn't call the ctor for gimplify_omp_ctx. For now placement new is
>>>>> probably the simplest way to get what you want.
>>>>>
>>>> Thanks for pointing this out. I'll do it the way c->privatized_types has been allocated.
>>>> e.g., by making c->variables a pointer to std::map and c->variables = new gimplify_tree_t;
>>>>
>>>>
>>>>> -static void
>>>>> -delete_omp_context (struct gimplify_omp_ctx *c)
>>>>> -{
>>>>> - splay_tree_delete (c->variables);
>>>>> - delete c->privatized_types;
>>>>> - XDELETE (c);
>>>>> -}
>>>>>
>>>>> hm, why?
>>>>>
>>>> My bad, I'll restore this.
>>>>
>>>>> -gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
>>>>> +gimplify_adjust_omp_clauses_1 (std::pair<tree, unsigned> n, void *data)
>>>>>
>>>>> You can now change the type of data from void * to const
>>>>> gimplify_adjust_omp_clauses_data *
>>>>
>>>> Done!
>>>>
>>>>
>>>> Thanks for the feedback, they were really helpful. I have updated the patch. Please review this.
>>>> Also, although I run `make check` while compiling gcc (with bootstrap enabled), I'm not sure if 'omp' related tests were exercised.
>>>> I'm still unfamiliar with several components of gcc. Any pointers on how to ensure all tests were run, would be useful.
>>>
>>> I'm not sure we want to use std::map. Can you use GCCs own hash_map
>>> here?
>>
>> Ok, I'll try to use has_map. I was under the impression that we can use standard library features, that's why I used std::map.
>>
> Using std::map caused a bootstrap build problem on AIX.
> see: https://gcc.gnu.org/ml/gcc-patches/2014-10/msg02608.html
> However I am not sure if that's true any more after the following fix
> was commmited:
> https://gcc.gnu.org/ml/libstdc++/2014-10/msg00195.html
>
Thanks for letting me know.
-Aditya
> Regards,
> Prathamesh
>> Thanks,
>> -Aditya
>>
>>>
>>> Richard.
>>>
>>>>
>>>> -Aditya
>>>>
>>>>
>>>>
>>>>
>>>>>
>>>>> thanks!
>>>>>
>>>>> Trev
>>>>>
>>>>> On Fri, Mar 13, 2015 at 07:32:03PM +0000, Aditya K wrote:
>>>>>> You're right. I'll change this to:
>>>>>>
>>>>>> /* 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);
>>>>>> }
>>>>>> };
>>>>>>
>>>>>> New patch attached.
>>>>>>
>>>>>>
>>>>>> Thanks,
>>>>>> -Aditya
>>>>>>
>>>>>>
>>>>>> ----------------------------------------
>>>>>>> Date: Fri, 13 Mar 2015 19:02:11 +0000
>>>>>>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>>>>>> From: jwakely.gcc@gmail.com
>>>>>>> To: hiraditya@msn.com
>>>>>>> CC: richard.guenther@gmail.com; stevenb.gcc@gmail.com; gcc@gcc.gnu.org
>>>>>>>
>>>>>>> Are you sure your compare_variables functor is correct?
>>>>>>>
>>>>>>> Subtracting the two values seems very strange for a strict weak ordering.
>>>>>>>
>>>>>>> (Also "compare_variables" is a pretty poor name!)
>>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>>
>>
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-18 18:14 ` Aditya K
@ 2015-03-30 22:28 ` Aditya K
2015-03-31 7:09 ` Thomas Schwinge
0 siblings, 1 reply; 26+ messages in thread
From: Aditya K @ 2015-03-30 22:28 UTC (permalink / raw)
To: Prathamesh Kulkarni; +Cc: Richard Biener, Trevor Saunders, gcc
[-- Attachment #1: Type: text/plain, Size: 6394 bytes --]
So I have modified the patch to use hash_map instead of std::map. The patch is attached.
However, I got one regression after that.
# Comparing directories
## Dir1=../build-pristine/: 11 sum files
## Dir2=../build-test/: 11 sum files
# Comparing 11 common sum files
## /bin/sh ../contrib/compare_tests /tmp/gxx-sum1.29214 /tmp/gxx-sum2.29214
Tests that now fail, but worked before:
c-c++-common/goacc/loop-private-1.c -std=c++98 scan-tree-dump-times gimple "#pragma acc loop collapse\\(2\\) private\\(j\\) private\\(i\\)" 1
c-c++-common/goacc/loop-private-1.c scan-tree-dump-times gimple "#pragma acc loop collapse\\(2\\) private\\(j\\) private\\(i\\)" 1
## Differences found:
# 1 differences in 11 common sum files found
The error is due to mis-comparison because of reordering of private(i) private(j).
I wanted to know if the order of the private flags matter.
Thanks,
-Aditya
----------------------------------------
> From: hiraditya@msn.com
> To: prathamesh.kulkarni@linaro.org
> CC: richard.guenther@gmail.com; tbsaunde@tbsaunde.org; gcc@gcc.gnu.org
> Subject: RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> Date: Wed, 18 Mar 2015 18:14:49 +0000
>
>
>
> ----------------------------------------
>> Date: Wed, 18 Mar 2015 22:01:18 +0530
>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>> From: prathamesh.kulkarni@linaro.org
>> To: hiraditya@msn.com
>> CC: richard.guenther@gmail.com; tbsaunde@tbsaunde.org; gcc@gcc.gnu.org
>>
>> On 18 March 2015 at 21:20, Aditya K <hiraditya@msn.com> wrote:
>>>
>>>
>>> ----------------------------------------
>>>> Date: Wed, 18 Mar 2015 11:50:16 +0100
>>>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>>> From: richard.guenther@gmail.com
>>>> To: hiraditya@msn.com
>>>> CC: tbsaunde@tbsaunde.org; gcc@gcc.gnu.org
>>>>
>>>> On Mon, Mar 16, 2015 at 4:33 AM, Aditya K <hiraditya@msn.com> wrote:
>>>>>
>>>>>
>>>>> ----------------------------------------
>>>>>> Date: Sun, 15 Mar 2015 02:32:23 -0400
>>>>>> From: tbsaunde@tbsaunde.org
>>>>>> To: gcc@gcc.gnu.org
>>>>>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>>>>>
>>>>>> hi,
>>>>>>
>>>>>> I'm only commenting on algorithmic stuff at this point, you should make
>>>>>> sure this doesn't regress anything in make check. This stuff only
>>>>>> effects code using omp stuff so compiling random c++ is unlikely to test
>>>>>> this code at all.
>>>>>>
>>>>>> Also please follow the style in
>>>>>> https://gcc.gnu.org/codingconventions.html
>>>>>> and usually try to make new code similar to what's around it.
>>>>>>
>>>>>> @@ -384,7 +386,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 = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
>>>>>>
>>>>>> I don't think this is what you want, xcnew is a calloc wrapper and
>>>>>> doesn't call the ctor for gimplify_omp_ctx. For now placement new is
>>>>>> probably the simplest way to get what you want.
>>>>>>
>>>>> Thanks for pointing this out. I'll do it the way c->privatized_types has been allocated.
>>>>> e.g., by making c->variables a pointer to std::map and c->variables = new gimplify_tree_t;
>>>>>
>>>>>
>>>>>> -static void
>>>>>> -delete_omp_context (struct gimplify_omp_ctx *c)
>>>>>> -{
>>>>>> - splay_tree_delete (c->variables);
>>>>>> - delete c->privatized_types;
>>>>>> - XDELETE (c);
>>>>>> -}
>>>>>>
>>>>>> hm, why?
>>>>>>
>>>>> My bad, I'll restore this.
>>>>>
>>>>>> -gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
>>>>>> +gimplify_adjust_omp_clauses_1 (std::pair<tree, unsigned> n, void *data)
>>>>>>
>>>>>> You can now change the type of data from void * to const
>>>>>> gimplify_adjust_omp_clauses_data *
>>>>>
>>>>> Done!
>>>>>
>>>>>
>>>>> Thanks for the feedback, they were really helpful. I have updated the patch. Please review this.
>>>>> Also, although I run `make check` while compiling gcc (with bootstrap enabled), I'm not sure if 'omp' related tests were exercised.
>>>>> I'm still unfamiliar with several components of gcc. Any pointers on how to ensure all tests were run, would be useful.
>>>>
>>>> I'm not sure we want to use std::map. Can you use GCCs own hash_map
>>>> here?
>>>
>>> Ok, I'll try to use has_map. I was under the impression that we can use standard library features, that's why I used std::map.
>>>
>> Using std::map caused a bootstrap build problem on AIX.
>> see: https://gcc.gnu.org/ml/gcc-patches/2014-10/msg02608.html
>> However I am not sure if that's true any more after the following fix
>> was commmited:
>> https://gcc.gnu.org/ml/libstdc++/2014-10/msg00195.html
>>
>
> Thanks for letting me know.
> -Aditya
>
>> Regards,
>> Prathamesh
>>> Thanks,
>>> -Aditya
>>>
>>>>
>>>> Richard.
>>>>
>>>>>
>>>>> -Aditya
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>>
>>>>>> thanks!
>>>>>>
>>>>>> Trev
>>>>>>
>>>>>> On Fri, Mar 13, 2015 at 07:32:03PM +0000, Aditya K wrote:
>>>>>>> You're right. I'll change this to:
>>>>>>>
>>>>>>> /* 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);
>>>>>>> }
>>>>>>> };
>>>>>>>
>>>>>>> New patch attached.
>>>>>>>
>>>>>>>
>>>>>>> Thanks,
>>>>>>> -Aditya
>>>>>>>
>>>>>>>
>>>>>>> ----------------------------------------
>>>>>>>> Date: Fri, 13 Mar 2015 19:02:11 +0000
>>>>>>>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>>>>>>>> From: jwakely.gcc@gmail.com
>>>>>>>> To: hiraditya@msn.com
>>>>>>>> CC: richard.guenther@gmail.com; stevenb.gcc@gmail.com; gcc@gcc.gnu.org
>>>>>>>>
>>>>>>>> Are you sure your compare_variables functor is correct?
>>>>>>>>
>>>>>>>> Subtracting the two values seems very strange for a strict weak ordering.
>>>>>>>>
>>>>>>>> (Also "compare_variables" is a pretty poor name!)
>>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>>
>>>
>
[-- Attachment #2: splay_tree.patch --]
[-- Type: application/octet-stream, Size: 20206 bytes --]
commit 1a0a8870b10711e7d300ecfcdac2e7aa8d99c429
Author: Aditya Kumar <aditya.k7@samsung.com>
Date: Mon Mar 16 10:09:06 2015 -0500
Remove splay_tree from gimplify.c
diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index d822913..18c4b1f 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -92,6 +92,21 @@ 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 xa == 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 +181,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 +379,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 +388,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 +405,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 +1097,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)
@@ -5522,20 +5525,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;
}
@@ -5612,7 +5615,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;
@@ -5625,19 +5628,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;
}
@@ -5706,9 +5709,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.
@@ -5720,36 +5723,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;
}
@@ -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::data_type *n;
unsigned flags = in_code ? GOVD_SEEN : 0;
bool ret = false, shared;
@@ -5784,7 +5787,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);
@@ -5802,9 +5805,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;
}
@@ -5867,12 +5870,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;
@@ -5907,28 +5910,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
@@ -5947,12 +5951,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)
{
@@ -5962,30 +5966,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));
}
@@ -6009,7 +6013,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
{
@@ -6025,9 +6029,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);
@@ -6390,13 +6394,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,9 +6432,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;
@@ -6519,7 +6523,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))
@@ -6529,16 +6534,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;
@@ -6551,21 +6557,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))
@@ -6578,38 +6586,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;
@@ -6619,8 +6626,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;
@@ -6629,8 +6636,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
@@ -6744,7 +6752,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);
@@ -6958,12 +6969,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)
{
@@ -6992,10 +7002,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 e1dea91..4f5c459 100644
--- a/gcc/hash-map.h
+++ b/gcc/hash-map.h
@@ -188,6 +188,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. */
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-30 22:28 ` Aditya K
@ 2015-03-31 7:09 ` Thomas Schwinge
2015-03-31 21:47 ` Aditya K
0 siblings, 1 reply; 26+ messages in thread
From: Thomas Schwinge @ 2015-03-31 7:09 UTC (permalink / raw)
To: Aditya K; +Cc: Richard Biener, Trevor Saunders, gcc, Prathamesh Kulkarni
[-- Attachment #1: Type: text/plain, Size: 1135 bytes --]
Hi!
On Mon, 30 Mar 2015 22:28:41 +0000, Aditya K <hiraditya@msn.com> wrote:
> So I have modified the patch to use hash_map instead of std::map. The patch is attached.
>
> However, I got one regression after that.
>
> # Comparing directories
> ## Dir1=../build-pristine/: 11 sum files
> ## Dir2=../build-test/: 11 sum files
>
> # Comparing 11 common sum files
> ## /bin/sh ../contrib/compare_tests /tmp/gxx-sum1.29214 /tmp/gxx-sum2.29214
> Tests that now fail, but worked before:
>
> c-c++-common/goacc/loop-private-1.c -std=c++98 scan-tree-dump-times gimple "#pragma acc loop collapse\\(2\\) private\\(j\\) private\\(i\\)" 1
> c-c++-common/goacc/loop-private-1.c scan-tree-dump-times gimple "#pragma acc loop collapse\\(2\\) private\\(j\\) private\\(i\\)" 1
>
> ## Differences found:
> # 1 differences in 11 common sum files found
>
>
> The error is due to mis-comparison because of reordering of private(i) private(j).
>
> I wanted to know if the order of the private flags matter.
It doesn't matter. (I have not reviewed the proposed changes/patches
themselves.)
Grüße,
Thomas
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 472 bytes --]
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-31 7:09 ` Thomas Schwinge
@ 2015-03-31 21:47 ` Aditya K
0 siblings, 0 replies; 26+ messages in thread
From: Aditya K @ 2015-03-31 21:47 UTC (permalink / raw)
To: Thomas Schwinge; +Cc: Richard Biener, Trevor Saunders, gcc, Prathamesh Kulkarni
----------------------------------------
> From: thomas@codesourcery.com
> To: hiraditya@msn.com
> CC: richard.guenther@gmail.com; tbsaunde@tbsaunde.org; gcc@gcc.gnu.org; prathamesh.kulkarni@linaro.org
> Subject: RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> Date: Tue, 31 Mar 2015 09:09:24 +0200
>
> Hi!
>
> On Mon, 30 Mar 2015 22:28:41 +0000, Aditya K <hiraditya@msn.com> wrote:
>> So I have modified the patch to use hash_map instead of std::map. The patch is attached.
>>
>> However, I got one regression after that.
>>
>> # Comparing directories
>> ## Dir1=../build-pristine/: 11 sum files
>> ## Dir2=../build-test/: 11 sum files
>>
>> # Comparing 11 common sum files
>> ## /bin/sh ../contrib/compare_tests /tmp/gxx-sum1.29214 /tmp/gxx-sum2.29214
>> Tests that now fail, but worked before:
>>
>> c-c++-common/goacc/loop-private-1.c -std=c++98 scan-tree-dump-times gimple "#pragma acc loop collapse\\(2\\) private\\(j\\) private\\(i\\)" 1
>> c-c++-common/goacc/loop-private-1.c scan-tree-dump-times gimple "#pragma acc loop collapse\\(2\\) private\\(j\\) private\\(i\\)" 1
>>
>> ## Differences found:
>> # 1 differences in 11 common sum files found
>>
>>
>> The error is due to mis-comparison because of reordering of private(i) private(j).
>>
>> I wanted to know if the order of the private flags matter.
>
> It doesn't matter. (I have not reviewed the proposed changes/patches
> themselves.)
>
Previously, I replaced splay_tree with std::map, and there were no regressions. I'm thinking this was because, std::map provides iterators to traverse the elements in a deterministic order (the sorted order) but
hash_map iterators may not have that order.
Thanks,
-Aditya
>
> Grüße,
> Thomas
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-16 18:45 ` Aditya K
@ 2015-03-16 21:25 ` Aditya K
0 siblings, 0 replies; 26+ messages in thread
From: Aditya K @ 2015-03-16 21:25 UTC (permalink / raw)
To: Manuel López-Ibáñez, Jonathan Wakely
Cc: Trevor Saunders, gcc Mailing List
----------------------------------------
> From: hiraditya@msn.com
> To: lopezibanez@gmail.com; jwakely.gcc@gmail.com
> CC: tbsaunde@tbsaunde.org; gcc@gcc.gnu.org
> Subject: RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> Date: Mon, 16 Mar 2015 18:45:22 +0000
>
>
>
> ----------------------------------------
>> From: lopezibanez@gmail.com
>> Date: Mon, 16 Mar 2015 17:04:58 +0100
>> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
>> To: jwakely.gcc@gmail.com
>> CC: hiraditya@msn.com; tbsaunde@tbsaunde.org; gcc@gcc.gnu.org
>>
>> On 16 March 2015 at 16:55, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
>>> On 16 March 2015 at 15:54, Jonathan Wakely wrote:
>>>> "DejaGnu" is not meant to be a link, but the wiki automatically treats
>>>> any MixedCase word as a link.
>>>
>>> I've fixed that now.
>>
>> We can actually link to the DejaGNU page if someone is interested. But
>> probably they only need to find it on their own GNU/Linux, so I
>> mention that as well.
>>
>> Aditya, I hope it is clear now.
>
> Yes it is. Thanks.
>
> -Aditya
So I tested my patch, and there were no regressions in the make check
Please review the patch:
http://gcc.gnu.org/ml/gcc/2015-03/msg00179/splay.patch
Thanks,
-Aditya
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-16 16:05 ` Manuel López-Ibáñez
@ 2015-03-16 18:45 ` Aditya K
2015-03-16 21:25 ` Aditya K
0 siblings, 1 reply; 26+ messages in thread
From: Aditya K @ 2015-03-16 18:45 UTC (permalink / raw)
To: Manuel López-Ibáñez, Jonathan Wakely
Cc: Trevor Saunders, gcc Mailing List
----------------------------------------
> From: lopezibanez@gmail.com
> Date: Mon, 16 Mar 2015 17:04:58 +0100
> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> To: jwakely.gcc@gmail.com
> CC: hiraditya@msn.com; tbsaunde@tbsaunde.org; gcc@gcc.gnu.org
>
> On 16 March 2015 at 16:55, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
>> On 16 March 2015 at 15:54, Jonathan Wakely wrote:
>>> "DejaGnu" is not meant to be a link, but the wiki automatically treats
>>> any MixedCase word as a link.
>>
>> I've fixed that now.
>
> We can actually link to the DejaGNU page if someone is interested. But
> probably they only need to find it on their own GNU/Linux, so I
> mention that as well.
>
> Aditya, I hope it is clear now.
Yes it is. Thanks.
-Aditya
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-16 15:55 ` Jonathan Wakely
@ 2015-03-16 16:05 ` Manuel López-Ibáñez
2015-03-16 18:45 ` Aditya K
0 siblings, 1 reply; 26+ messages in thread
From: Manuel López-Ibáñez @ 2015-03-16 16:05 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: Aditya K, Trevor Saunders, gcc Mailing List
On 16 March 2015 at 16:55, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
> On 16 March 2015 at 15:54, Jonathan Wakely wrote:
>> "DejaGnu" is not meant to be a link, but the wiki automatically treats
>> any MixedCase word as a link.
>
> I've fixed that now.
We can actually link to the DejaGNU page if someone is interested. But
probably they only need to find it on their own GNU/Linux, so I
mention that as well.
Aditya, I hope it is clear now.
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-16 15:54 ` Jonathan Wakely
@ 2015-03-16 15:55 ` Jonathan Wakely
2015-03-16 16:05 ` Manuel López-Ibáñez
0 siblings, 1 reply; 26+ messages in thread
From: Jonathan Wakely @ 2015-03-16 15:55 UTC (permalink / raw)
To: Aditya K
Cc: Manuel López-Ibáñez, Trevor Saunders, gcc Mailing List
On 16 March 2015 at 15:54, Jonathan Wakely wrote:
> "DejaGnu" is not meant to be a link, but the wiki automatically treats
> any MixedCase word as a link.
I've fixed that now.
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-16 15:51 ` Aditya K
@ 2015-03-16 15:54 ` Jonathan Wakely
2015-03-16 15:55 ` Jonathan Wakely
0 siblings, 1 reply; 26+ messages in thread
From: Jonathan Wakely @ 2015-03-16 15:54 UTC (permalink / raw)
To: Aditya K
Cc: Manuel López-Ibáñez, Trevor Saunders, gcc Mailing List
On 16 March 2015 at 15:51, Aditya K wrote:
> I started looking at the steps to test gcc, (https://gcc.gnu.org/Testing_GCC):
>
> In the first step: to install prerequisites 'dejagnu', tcl and Expect
> - The link to dejagnu does not have any information. for tcl and expect there are no links.
"DejaGnu" is not meant to be a link, but the wiki automatically treats
any MixedCase word as a link.
You don't need links about them, you need to have them installed.
^ permalink raw reply [flat|nested] 26+ messages in thread
* RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).
2015-03-16 14:17 Manuel López-Ibáñez
@ 2015-03-16 15:51 ` Aditya K
2015-03-16 15:54 ` Jonathan Wakely
0 siblings, 1 reply; 26+ messages in thread
From: Aditya K @ 2015-03-16 15:51 UTC (permalink / raw)
To: Manuel López-Ibáñez, Trevor Saunders, gcc Mailing List
----------------------------------------
> From: lopezibanez@gmail.com
> Date: Mon, 16 Mar 2015 15:16:55 +0100
> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> To: tbsaunde@tbsaunde.org; gcc@gcc.gnu.org; hiraditya@msn.com
>
>>> Thanks for the feedback, they were really helpful. I have updated the patch. Please review this.
>>> Also, although I run `make check` while compiling gcc (with bootstrap enabled), I'm not sure if 'omp' related tests were exercised.
>>> I'm still unfamiliar with several components of gcc. Any pointers on how to ensure all tests were run, would be useful.
>>
>>
>> https://gcc.gnu.org/install/test.html should help, though unfortunately
>> you'll probably find the easiest way to check for regressions is to do
>> one run of straight trunk, then another with your patch. Saddly a bunch
>> of people have own scripts to deal with administrivia, but there isn't a
>> standardized way that's simple.
>
> I would recommend going through
>
> https://gcc.gnu.org/wiki/GettingStarted#Basics:_Contributing_to_GCC_in_10_easy_steps
>
> at least once. If you find something wrong, confusing or not answered
> there, please ask here and CC me, and I will NOT answer you ;) what I
> will do is update it, so the answer is there for you but also for the
> next person that comes after you.
>
> Of course, it is a wiki, anyone can update it and they are welcome to do it.
>
> Cheers,
>
> Manuel.
Hi Manuel,
I started looking at the steps to test gcc, (https://gcc.gnu.org/Testing_GCC):
In the first step: to install prerequisites 'dejagnu', tcl and Expect
- The link to dejagnu does not have any information. for tcl and expect there are no links.
Thanks,
-Aditya
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
@ 2015-03-16 14:17 Manuel López-Ibáñez
2015-03-16 15:51 ` Aditya K
0 siblings, 1 reply; 26+ messages in thread
From: Manuel López-Ibáñez @ 2015-03-16 14:17 UTC (permalink / raw)
To: Trevor Saunders, gcc Mailing List, hiraditya
>> Thanks for the feedback, they were really helpful. I have updated the patch. Please review this.
>> Also, although I run `make check` while compiling gcc (with bootstrap enabled), I'm not sure if 'omp' related tests were exercised.
>> I'm still unfamiliar with several components of gcc. Any pointers on how to ensure all tests were run, would be useful.
>
>
> https://gcc.gnu.org/install/test.html should help, though unfortunately
> you'll probably find the easiest way to check for regressions is to do
> one run of straight trunk, then another with your patch. Saddly a bunch
> of people have own scripts to deal with administrivia, but there isn't a
> standardized way that's simple.
I would recommend going through
https://gcc.gnu.org/wiki/GettingStarted#Basics:_Contributing_to_GCC_in_10_easy_steps
at least once. If you find something wrong, confusing or not answered
there, please ask here and CC me, and I will NOT answer you ;) what I
will do is update it, so the answer is there for you but also for the
next person that comes after you.
Of course, it is a wiki, anyone can update it and they are welcome to do it.
Cheers,
Manuel.
^ permalink raw reply [flat|nested] 26+ messages in thread
end of thread, other threads:[~2015-03-31 21:47 UTC | newest]
Thread overview: 26+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-03-09 18:59 Proposal for adding splay_tree_find (to find elements without updating the nodes) vax mzn
2015-03-09 19:26 ` Trevor Saunders
2015-03-09 21:02 ` Aditya K
2015-03-09 23:00 ` Steven Bosscher
2015-03-10 4:05 ` Aditya K
2015-03-10 10:20 ` Richard Biener
2015-03-13 18:51 ` Aditya K
2015-03-13 19:02 ` Jonathan Wakely
2015-03-13 19:32 ` Aditya K
2015-03-15 6:33 ` Trevor Saunders
2015-03-16 3:33 ` Aditya K
2015-03-16 4:17 ` Trevor Saunders
2015-03-18 10:50 ` Richard Biener
2015-03-18 15:50 ` Aditya K
2015-03-18 16:31 ` Prathamesh Kulkarni
2015-03-18 18:14 ` Aditya K
2015-03-30 22:28 ` Aditya K
2015-03-31 7:09 ` Thomas Schwinge
2015-03-31 21:47 ` Aditya K
2015-03-16 14:17 Manuel López-Ibáñez
2015-03-16 15:51 ` Aditya K
2015-03-16 15:54 ` Jonathan Wakely
2015-03-16 15:55 ` Jonathan Wakely
2015-03-16 16:05 ` Manuel López-Ibáñez
2015-03-16 18:45 ` Aditya K
2015-03-16 21:25 ` 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).