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

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.

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);
>

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

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

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

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,