Patchwork [c++] convert arg_lookup.{classes,namespaces} to VECs

login
register
mail settings
Submitter Nathan Froyd
Date June 16, 2010, 9:19 p.m.
Message ID <20100616211951.GJ27105@codesourcery.com>
Download mbox | patch
Permalink /patch/55938/
State New
Headers show

Comments

Nathan Froyd - June 16, 2010, 9:19 p.m.
AS $SUBEJCT suggests.  Removal of TREE_LISTs in an area which has its
own timevar can't be a bad thing.

The only interesting part of this patch is the middle-end changes, which
I need separate approval for.  vec_member can be used in other followup
patches as well.

Tested x86_64-unknown-linux-gnu.

-Nathan

gcc/
	* tree.h (vec_member): Declare.
	* tree.c (vec_member): Define.

gcc/cp/
	* name-lookup.c (struct arg_lookup): Convert namesspaces and
        classes fields to VEC.
	(arg_assoc_namespace): Adjust for new type of namespaces.
	(arg_assoc_class): Adjust for new type of classes.
	(lookup_arg_dependent): Use make_tree_vector and
        release_tree_vector.
	* typeck2.c (build_x_arrow): Use vec_member.
Richard Guenther - June 16, 2010, 9:38 p.m.
On Wed, Jun 16, 2010 at 11:19 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
> AS $SUBEJCT suggests.  Removal of TREE_LISTs in an area which has its
> own timevar can't be a bad thing.
>
> The only interesting part of this patch is the middle-end changes, which
> I need separate approval for.  vec_member can be used in other followup
> patches as well.

Err - while this is sort-of a 1:1 transform the code looks quadratic and asks
for some other data structure, no?

Richard.

> Tested x86_64-unknown-linux-gnu.
>
> -Nathan
>
> gcc/
>        * tree.h (vec_member): Declare.
>        * tree.c (vec_member): Define.
>
> gcc/cp/
>        * name-lookup.c (struct arg_lookup): Convert namesspaces and
>        classes fields to VEC.
>        (arg_assoc_namespace): Adjust for new type of namespaces.
>        (arg_assoc_class): Adjust for new type of classes.
>        (lookup_arg_dependent): Use make_tree_vector and
>        release_tree_vector.
>        * typeck2.c (build_x_arrow): Use vec_member.
>
> diff --git a/gcc/cp/name-lookup.c b/gcc/cp/name-lookup.c
> index 0c759c6..2643e8c 100644
> --- a/gcc/cp/name-lookup.c
> +++ b/gcc/cp/name-lookup.c
> @@ -4589,8 +4589,8 @@ struct arg_lookup
>  {
>   tree name;
>   VEC(tree,gc) *args;
> -  tree namespaces;
> -  tree classes;
> +  VEC(tree,gc) *namespaces;
> +  VEC(tree,gc) *classes;
>   tree functions;
>  };
>
> @@ -4667,9 +4667,9 @@ arg_assoc_namespace (struct arg_lookup *k, tree scope)
>  {
>   tree value;
>
> -  if (purpose_member (scope, k->namespaces))
> -    return 0;
> -  k->namespaces = tree_cons (scope, NULL_TREE, k->namespaces);
> +  if (vec_member (scope, k->namespaces))
> +    return false;
> +  VEC_safe_push (tree, gc, k->namespaces, scope);
>
>   /* Check out our super-users.  */
>   for (value = DECL_NAMESPACE_ASSOCIATIONS (scope); value;
> @@ -4850,9 +4850,9 @@ arg_assoc_class (struct arg_lookup *k, tree type)
>   if (!CLASS_TYPE_P (type))
>     return false;
>
> -  if (purpose_member (type, k->classes))
> +  if (vec_member (type, k->classes))
>     return false;
> -  k->classes = tree_cons (type, NULL_TREE, k->classes);
> +  VEC_safe_push (tree, gc, k->classes, type);
>
>   if (TYPE_CLASS_SCOPE_P (type)
>       && arg_assoc_class_only (k, TYPE_CONTEXT (type)))
> @@ -5049,14 +5049,14 @@ lookup_arg_dependent (tree name, tree fns, VEC(tree,gc) *args)
>   k.name = name;
>   k.args = args;
>   k.functions = fns;
> -  k.classes = NULL_TREE;
> +  k.classes = make_tree_vector ();
>
>   /* We previously performed an optimization here by setting
>      NAMESPACES to the current namespace when it was safe. However, DR
>      164 says that namespaces that were already searched in the first
>      stage of template processing are searched again (potentially
>      picking up later definitions) in the second stage. */
> -  k.namespaces = NULL_TREE;
> +  k.namespaces = make_tree_vector ();
>
>   arg_assoc_args_vec (&k, args);
>
> @@ -5070,6 +5070,9 @@ lookup_arg_dependent (tree name, tree fns, VEC(tree,gc) *args)
>       error ("  in call to %qD", name);
>       fns = error_mark_node;
>     }
> +
> +  release_tree_vector (k.classes);
> +  release_tree_vector (k.namespaces);
>
>   POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, fns);
>  }
> diff --git a/gcc/cp/typeck2.c b/gcc/cp/typeck2.c
> index e7b97c4..7aed503 100644
> --- a/gcc/cp/typeck2.c
> +++ b/gcc/cp/typeck2.c
> @@ -1419,18 +1419,14 @@ build_x_arrow (tree expr)
>                                   /*overloaded_p=*/NULL,
>                                   tf_warning_or_error)))
>        {
> -         tree t;
> -         unsigned ix;
> -
>          if (expr == error_mark_node)
>            return error_mark_node;
>
> -         for (ix = 0; VEC_iterate (tree, types_memoized, ix, t); ix++)
> -           if (TREE_TYPE (expr) == t)
> -             {
> -               error ("circular pointer delegation detected");
> -               return error_mark_node;
> -             }
> +         if (vec_member (TREE_TYPE (expr), types_memoized))
> +           {
> +             error ("circular pointer delegation detected");
> +             return error_mark_node;
> +           }
>
>          VEC_safe_push (tree, gc, types_memoized, TREE_TYPE (expr));
>          last_rval = expr;
> diff --git a/gcc/tree.c b/gcc/tree.c
> index 67e2f41..cb8e4fe 100644
> --- a/gcc/tree.c
> +++ b/gcc/tree.c
> @@ -1923,6 +1923,19 @@ purpose_member (const_tree elem, tree list)
>   return NULL_TREE;
>  }
>
> +/* Return true if ELEM is in V.  */
> +
> +bool
> +vec_member (const_tree elem, VEC(tree,gc) *v)
> +{
> +  unsigned ix;
> +  tree t;
> +  for (ix = 0; VEC_iterate (tree, v, ix, t); ix++)
> +    if (elem == t)
> +      return true;
> +  return false;
> +}
> +
>  /* Returns element number IDX (zero-origin) of chain CHAIN, or
>    NULL_TREE.  */
>
> diff --git a/gcc/tree.h b/gcc/tree.h
> index 13c684a..a70608e 100644
> --- a/gcc/tree.h
> +++ b/gcc/tree.h
> @@ -4086,6 +4086,7 @@ extern bool range_in_array_bounds_p (tree);
>
>  extern tree value_member (tree, tree);
>  extern tree purpose_member (const_tree, tree);
> +extern bool vec_member (const_tree, VEC(tree,gc) *);
>  extern tree chain_index (int, tree);
>
>  extern int attribute_list_equal (const_tree, const_tree);
>
Andrew Pinski - June 16, 2010, 9:42 p.m.
On Wed, Jun 16, 2010 at 2:38 PM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> Err - while this is sort-of a 1:1 transform the code looks quadratic and asks
> for some other data structure, no?

It does look like a pointer_map_t will fit better as you never remove
anything from it.  And you only queue if something is in the set
already.

Thanks,
Andrew Pinski
Paolo Bonzini - June 16, 2010, 10:18 p.m.
On 06/16/2010 11:42 PM, Andrew Pinski wrote:
> On Wed, Jun 16, 2010 at 2:38 PM, Richard Guenther
> <richard.guenther@gmail.com>  wrote:
>> Err - while this is sort-of a 1:1 transform the code looks quadratic and asks
>> for some other data structure, no?
>
> It does look like a pointer_map_t will fit better as you never remove
> anything from it.  And you only queue if something is in the set
> already.

You mean pointer_set. :)

Paolo
Nathan Froyd - June 17, 2010, 2:27 a.m.
On Wed, Jun 16, 2010 at 11:38:12PM +0200, Richard Guenther wrote:
> On Wed, Jun 16, 2010 at 11:19 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
> > AS $SUBEJCT suggests.  Removal of TREE_LISTs in an area which has its
> > own timevar can't be a bad thing.
> >
> > The only interesting part of this patch is the middle-end changes, which
> > I need separate approval for.  vec_member can be used in other followup
> > patches as well.
> 
> Err - while this is sort-of a 1:1 transform the code looks quadratic and asks
> for some other data structure, no?

Err - maybe.  Compiling monotone (~70KLOC) with an instrumented g++ to
record the lengths of the namespace and classes VECs after finishing arg
lookup gave these stats for namespaces:

0 27444
1 39095
2 24602
3 8140
4 915
5 57
6 33
7 2
9 1

and for classes:

0 42909
1 18318
2 8790
3 15245
4 6882
5 3397
6 2026
7 859
8 623
9 758
10 217
11 112
12 59
13 17
21 2
14 22
22 1
15 12
16 8
23 1
17 26
24 1
18 4

(blame gawk for not sorting things properly.  I don't claim that
monotone is particularly representative of all C++ apps, but it's a
decent sized one that's easy to build)

Anyway, that's about 100K calls over the whole program.  99% of the
calls have 4 namespaces or less.  90% of the calls have 4 classes or
less.  I agree that using a vector for sets is not worst-case efficient,
but for the majority of uses here, I think a vector is just as efficient
as a pointer_set.

The patch as-is is a strict improvement.  I'm happy to rewrite it to use
pointer_sets, but I think they're a little bulky for this use (by
default 256+ words of memory vs. a svelte ~10 that might have been used
recently).

-Nathan
Mark Mitchell - June 17, 2010, 4:19 p.m.
Nathan Froyd wrote:

> The patch as-is is a strict improvement

I agree.  Let's get it checked in.

There's nothing wrong with making further improvements, but there's no
reason not to take this one; it's a monotonic improvement in terms of
memory, performance, and readability.

Thanks,

Patch

diff --git a/gcc/cp/name-lookup.c b/gcc/cp/name-lookup.c
index 0c759c6..2643e8c 100644
--- a/gcc/cp/name-lookup.c
+++ b/gcc/cp/name-lookup.c
@@ -4589,8 +4589,8 @@  struct arg_lookup
 {
   tree name;
   VEC(tree,gc) *args;
-  tree namespaces;
-  tree classes;
+  VEC(tree,gc) *namespaces;
+  VEC(tree,gc) *classes;
   tree functions;
 };
 
@@ -4667,9 +4667,9 @@  arg_assoc_namespace (struct arg_lookup *k, tree scope)
 {
   tree value;
 
-  if (purpose_member (scope, k->namespaces))
-    return 0;
-  k->namespaces = tree_cons (scope, NULL_TREE, k->namespaces);
+  if (vec_member (scope, k->namespaces))
+    return false;
+  VEC_safe_push (tree, gc, k->namespaces, scope);
 
   /* Check out our super-users.  */
   for (value = DECL_NAMESPACE_ASSOCIATIONS (scope); value;
@@ -4850,9 +4850,9 @@  arg_assoc_class (struct arg_lookup *k, tree type)
   if (!CLASS_TYPE_P (type))
     return false;
 
-  if (purpose_member (type, k->classes))
+  if (vec_member (type, k->classes))
     return false;
-  k->classes = tree_cons (type, NULL_TREE, k->classes);
+  VEC_safe_push (tree, gc, k->classes, type);
 
   if (TYPE_CLASS_SCOPE_P (type)
       && arg_assoc_class_only (k, TYPE_CONTEXT (type)))
@@ -5049,14 +5049,14 @@  lookup_arg_dependent (tree name, tree fns, VEC(tree,gc) *args)
   k.name = name;
   k.args = args;
   k.functions = fns;
-  k.classes = NULL_TREE;
+  k.classes = make_tree_vector ();
 
   /* We previously performed an optimization here by setting
      NAMESPACES to the current namespace when it was safe. However, DR
      164 says that namespaces that were already searched in the first
      stage of template processing are searched again (potentially
      picking up later definitions) in the second stage. */
-  k.namespaces = NULL_TREE;
+  k.namespaces = make_tree_vector ();
 
   arg_assoc_args_vec (&k, args);
 
@@ -5070,6 +5070,9 @@  lookup_arg_dependent (tree name, tree fns, VEC(tree,gc) *args)
       error ("  in call to %qD", name);
       fns = error_mark_node;
     }
+
+  release_tree_vector (k.classes);
+  release_tree_vector (k.namespaces);
     
   POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, fns);
 }
diff --git a/gcc/cp/typeck2.c b/gcc/cp/typeck2.c
index e7b97c4..7aed503 100644
--- a/gcc/cp/typeck2.c
+++ b/gcc/cp/typeck2.c
@@ -1419,18 +1419,14 @@  build_x_arrow (tree expr)
 				   /*overloaded_p=*/NULL, 
 				   tf_warning_or_error)))
 	{
-	  tree t;
-	  unsigned ix;
-
 	  if (expr == error_mark_node)
 	    return error_mark_node;
 
-	  for (ix = 0; VEC_iterate (tree, types_memoized, ix, t); ix++)
-	    if (TREE_TYPE (expr) == t)
-	      {
-		error ("circular pointer delegation detected");
-		return error_mark_node;
-	      }
+	  if (vec_member (TREE_TYPE (expr), types_memoized))
+	    {
+	      error ("circular pointer delegation detected");
+	      return error_mark_node;
+	    }
 
 	  VEC_safe_push (tree, gc, types_memoized, TREE_TYPE (expr));
 	  last_rval = expr;
diff --git a/gcc/tree.c b/gcc/tree.c
index 67e2f41..cb8e4fe 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -1923,6 +1923,19 @@  purpose_member (const_tree elem, tree list)
   return NULL_TREE;
 }
 
+/* Return true if ELEM is in V.  */
+
+bool
+vec_member (const_tree elem, VEC(tree,gc) *v)
+{
+  unsigned ix;
+  tree t;
+  for (ix = 0; VEC_iterate (tree, v, ix, t); ix++)
+    if (elem == t)
+      return true;
+  return false;
+}
+
 /* Returns element number IDX (zero-origin) of chain CHAIN, or
    NULL_TREE.  */
 
diff --git a/gcc/tree.h b/gcc/tree.h
index 13c684a..a70608e 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -4086,6 +4086,7 @@  extern bool range_in_array_bounds_p (tree);
 
 extern tree value_member (tree, tree);
 extern tree purpose_member (const_tree, tree);
+extern bool vec_member (const_tree, VEC(tree,gc) *);
 extern tree chain_index (int, tree);
 
 extern int attribute_list_equal (const_tree, const_tree);