This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

(C++) patch to speed up Koenig lookup


One of our customers found that even with the optimization to use == in
equal_functions most of the time, arg_assoc_namespace was consuming 15% of
their compilation time.  And their code doesn't use namespaces.

This patch causes us not to redundantly consider namespaces that we already
saw in the normal lookup, and changes the creation of the function list
from O(n^2) to O(n) by not checking to see if a function is already
represented; there shouldn't be many duplicates, but if there are, we'll
handle them in joust.

1999-08-14  Jason Merrill  <jason@yorick.cygnus.com>

	Speed up Koenig lookup.
	* decl.c (unqualified_namespace_lookup): Nonstatic.  Add spacep parm
	to return namespaces we've looked at.
	* decl2.c (lookup_using_namespace): Likewise.
	(add_function): Don't call ovl_member.
	(lookup_arg_dependent): Initialize k.namespaces to the list of 
	namespaces seen in unqualified lookup.
	* call.c (equal_functions): Move here from tree.c.
	(joust): Use it to handle duplicate candidates.
	* tree.c (ovl_member): Use ==.

Index: call.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/cp/call.c,v
retrieving revision 1.161
diff -c -p -r1.161 call.c
*** call.c	1999/08/11 20:22:23	1.161
--- call.c	1999/08/14 10:46:41
*************** static tree build_new_method_call PROTO(
*** 44,49 ****
--- 44,50 ----
  
  static tree build_field_call PROTO((tree, tree, tree, tree));
  static struct z_candidate * tourney PROTO((struct z_candidate *));
+ static int equal_functions PROTO((tree, tree));
  static int joust PROTO((struct z_candidate *, struct z_candidate *, int));
  static int compare_ics PROTO((tree, tree));
  static tree build_over_call PROTO((struct z_candidate *, tree, int));
*************** add_warning (winner, loser)
*** 4791,4796 ****
--- 4792,4811 ----
  				     winner->warnings);
  }
  
+ /* Returns true iff functions are equivalent. Equivalent functions are
+    not identical only if one is a function-local extern function.
+    This assumes that function-locals don't have TREE_PERMANENT.  */
+ 
+ static inline int
+ equal_functions (fn1, fn2)
+      tree fn1;
+      tree fn2;
+ {
+   if (!TREE_PERMANENT (fn1) || !TREE_PERMANENT (fn2))
+     return decls_match (fn1, fn2);
+   return fn1 == fn2;
+ }
+ 
  /* Compare two candidates for overloading as described in
     [over.match.best].  Return values:
  
*************** joust (cand1, cand2, warn)
*** 4985,4990 ****
--- 5000,5011 ----
  	    }
  	}
      }
+ 
+   /* If the two functions are the same (this can happen with declarations
+      in multiple scopes and arg-dependent lookup), arbitrarily choose one.  */
+   if (DECL_P (cand1->fn) && DECL_P (cand2->fn)
+       && equal_functions (cand1->fn, cand2->fn))
+     return 1;
  
  tweak:
  
Index: cp-tree.h
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/cp/cp-tree.h,v
retrieving revision 1.261
diff -c -p -r1.261 cp-tree.h
*** cp-tree.h	1999/08/12 06:52:27	1.261
--- cp-tree.h	1999/08/14 10:46:42
*************** extern tree lookup_name_namespace_only  
*** 2868,2875 ****
  extern void begin_only_namespace_names          PROTO((void));
  extern void end_only_namespace_names            PROTO((void));
  extern tree namespace_ancestor			PROTO((tree, tree));
! extern int  lookup_using_namespace              PROTO((tree,tree,tree,tree,int));
! extern int  qualified_lookup_using_namespace    PROTO((tree,tree,tree,int));
  extern tree auto_function			PROTO((tree, tree, enum built_in_function));
  extern void init_decl_processing		PROTO((void));
  extern int init_type_desc			PROTO((void));
--- 2868,2876 ----
  extern void begin_only_namespace_names          PROTO((void));
  extern void end_only_namespace_names            PROTO((void));
  extern tree namespace_ancestor			PROTO((tree, tree));
! extern tree unqualified_namespace_lookup	PROTO((tree, int, tree *));
! extern int  lookup_using_namespace              PROTO((tree, tree, tree, tree, int, tree *));
! extern int  qualified_lookup_using_namespace    PROTO((tree, tree, tree, int));
  extern tree auto_function			PROTO((tree, tree, enum built_in_function));
  extern void init_decl_processing		PROTO((void));
  extern int init_type_desc			PROTO((void));
Index: decl.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/cp/decl.c,v
retrieving revision 1.405
diff -c -p -r1.405 decl.c
*** decl.c	1999/08/12 06:52:28	1.405
--- decl.c	1999/08/14 10:46:42
*************** static void pop_binding PROTO((tree, tre
*** 179,185 ****
  static tree local_variable_p PROTO((tree));
  static tree find_binding PROTO((tree, tree));
  static tree select_decl PROTO((tree, int));
- static tree unqualified_namespace_lookup PROTO((tree, int));
  static int lookup_flags PROTO((int, int));
  static tree qualify_lookup PROTO((tree, int));
  static tree record_builtin_java_type PROTO((const char *, int));
--- 179,184 ----
*************** select_decl (binding, flags)
*** 5515,5527 ****
    return val;
  }
  
! /* Unscoped lookup of a global, iterate over namespaces, considering
!    using namespace statements. */
  
! static tree
! unqualified_namespace_lookup (name, flags)
       tree name;
       int flags;
  {
    struct tree_binding _binding;
    tree b = binding_init (&_binding);
--- 5514,5528 ----
    return val;
  }
  
! /* Unscoped lookup of a global: iterate over current namespaces,
!    considering using-directives.  If SPACESP is non-NULL, store a list
!    of the namespaces we've considered in it.  */
  
! tree
! unqualified_namespace_lookup (name, flags, spacesp)
       tree name;
       int flags;
+      tree *spacesp;
  {
    struct tree_binding _binding;
    tree b = binding_init (&_binding);
*************** unqualified_namespace_lookup (name, flag
*** 5530,5538 ****
    tree siter;
    struct binding_level *level;
    tree val = NULL_TREE;
  
!   while (!val)
      {
        val = binding_for_name (name, scope);
  
        /* Initialize binding for this context. */
--- 5531,5544 ----
    tree siter;
    struct binding_level *level;
    tree val = NULL_TREE;
+ 
+   if (spacesp)
+     *spacesp = NULL_TREE;
  
!   for (; !val; scope = CP_DECL_CONTEXT (scope))
      {
+       if (spacesp)
+ 	*spacesp = scratch_tree_cons (scope, NULL_TREE, *spacesp);
        val = binding_for_name (name, scope);
  
        /* Initialize binding for this context. */
*************** unqualified_namespace_lookup (name, flag
*** 5544,5550 ****
  	   !level->namespace_p;
  	   level = level->level_chain)
  	if (!lookup_using_namespace (name, b, level->using_directives,
!                                      scope, flags))
  	  /* Give up because of error. */
  	  return error_mark_node;
  
--- 5550,5556 ----
  	   !level->namespace_p;
  	   level = level->level_chain)
  	if (!lookup_using_namespace (name, b, level->using_directives,
!                                      scope, flags, spacesp))
  	  /* Give up because of error. */
  	  return error_mark_node;
  
*************** unqualified_namespace_lookup (name, flag
*** 5554,5560 ****
        while (1)
  	{
  	  if (!lookup_using_namespace (name, b, DECL_NAMESPACE_USING (siter), 
! 				       scope, flags))
  	    /* Give up because of error. */
  	    return error_mark_node;
  	  if (siter == scope) break;
--- 5560,5566 ----
        while (1)
  	{
  	  if (!lookup_using_namespace (name, b, DECL_NAMESPACE_USING (siter), 
! 				       scope, flags, spacesp))
  	    /* Give up because of error. */
  	    return error_mark_node;
  	  if (siter == scope) break;
*************** unqualified_namespace_lookup (name, flag
*** 5564,5570 ****
        val = select_decl (b, flags);
        if (scope == global_namespace)
  	break;
-       scope = CP_DECL_CONTEXT (scope);
      }
    return val;
  }
--- 5570,5575 ----
*************** lookup_name_real (name, prefer_type, non
*** 5769,5775 ****
    /* Now lookup in namespace scopes.  */
    if (!val || val_is_implicit_typename)
      {
!       t = unqualified_namespace_lookup (name, flags);
        if (t)
  	{
  	  if (val_is_implicit_typename && !yylex)
--- 5774,5780 ----
    /* Now lookup in namespace scopes.  */
    if (!val || val_is_implicit_typename)
      {
!       t = unqualified_namespace_lookup (name, flags, 0);
        if (t)
  	{
  	  if (val_is_implicit_typename && !yylex)
Index: decl2.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/cp/decl2.c,v
retrieving revision 1.233
diff -c -p -r1.233 decl2.c
*** decl2.c	1999/08/12 06:52:29	1.233
--- decl2.c	1999/08/14 10:46:42
*************** ambiguous_decl (name, old, new, flags)
*** 4347,4360 ****
    return old;
  }
  
! /* Add the bindings of name in used namespaces to val.
!    The using list is defined by usings, and the lookup goes to scope.
     Returns zero on errors. */
  
  int
! lookup_using_namespace (name, val, usings, scope, flags)
       tree name, val, usings, scope;
       int flags;
  {
    tree iter;
    tree val1;
--- 4347,4364 ----
    return old;
  }
  
! /* Subroutine of unualified_namespace_lookup:
!    Add the bindings of NAME in used namespaces to VAL.
!    We are currently looking for names in namespace SCOPE, so we
!    look through USINGS for using-directives of namespaces
!    which have SCOPE as a common ancestor with the current scope.
     Returns zero on errors. */
  
  int
! lookup_using_namespace (name, val, usings, scope, flags, spacesp)
       tree name, val, usings, scope;
       int flags;
+      tree *spacesp;
  {
    tree iter;
    tree val1;
*************** lookup_using_namespace (name, val, using
*** 4363,4368 ****
--- 4367,4375 ----
    for (iter = usings; iter; iter = TREE_CHAIN (iter))
      if (TREE_VALUE (iter) == scope)
        {
+ 	if (spacesp)
+ 	  *spacesp = scratch_tree_cons (TREE_PURPOSE (iter), NULL_TREE,
+ 					*spacesp);
  	val1 = binding_for_name (name, TREE_PURPOSE (iter));
  	/* Resolve ambiguities. */
  	val = ambiguous_decl (name, val, val1, flags);
*************** add_function (k, fn)
*** 4571,4598 ****
       struct arg_lookup *k;
       tree fn;
  {
!   if (ovl_member (fn, k->functions))
!     return 0;
    /* We must find only functions, or exactly one non-function. */
    if (k->functions && is_overloaded_fn (k->functions)
        && is_overloaded_fn (fn))
      k->functions = build_overload (fn, k->functions);
!   else 
!     if(k->functions)
!       {
! 	tree f1 = OVL_CURRENT (k->functions);
! 	tree f2 = fn;
! 	if (is_overloaded_fn (f1))
! 	  {
! 	    fn = f1; f1 = f2; f2 = fn;
! 	  }
! 	cp_error_at ("`%D' is not a function,", f1);
! 	cp_error_at ("  conflict with `%D'", f2);
! 	cp_error ("  in call to `%D'", k->name);
! 	return 1;
!       }
!     else
!       k->functions = fn;
    return 0;
  }
  
--- 4578,4606 ----
       struct arg_lookup *k;
       tree fn;
  {
!   /* We used to check here to see if the function was already in the list,
!      but that's O(n^2), which is just too expensive for function lookup.
!      Now we deal with the occasional duplicate in joust.  */
! 
    /* We must find only functions, or exactly one non-function. */
    if (k->functions && is_overloaded_fn (k->functions)
        && is_overloaded_fn (fn))
      k->functions = build_overload (fn, k->functions);
!   else if (k->functions)
!     {
!       tree f1 = OVL_CURRENT (k->functions);
!       tree f2 = fn;
!       if (is_overloaded_fn (f1))
! 	{
! 	  fn = f1; f1 = f2; f2 = fn;
! 	}
!       cp_error_at ("`%D' is not a function,", f1);
!       cp_error_at ("  conflict with `%D'", f2);
!       cp_error ("  in call to `%D'", k->name);
!       return 1;
!     }
!   else
!     k->functions = fn;
    return 0;
  }
  
*************** arg_assoc_namespace (k, scope)
*** 4613,4619 ****
    value = namespace_binding (k->name, scope);
    if (!value)
      return 0;
!   
    for (; value; value = OVL_NEXT (value))
      if (add_function (k, OVL_CURRENT (value)))
        return 1;
--- 4621,4627 ----
    value = namespace_binding (k->name, scope);
    if (!value)
      return 0;
! 
    for (; value; value = OVL_NEXT (value))
      if (add_function (k, OVL_CURRENT (value)))
        return 1;
*************** lookup_arg_dependent (name, fns, args)
*** 4843,4853 ****
       tree args;
  {
    struct arg_lookup k;
    k.name = name;
    k.functions = fns;
-   k.namespaces = NULL_TREE;
    k.classes = NULL_TREE;
!   
    push_scratch_obstack ();
    arg_assoc_args (&k, args);
    pop_obstacks ();
--- 4851,4868 ----
       tree args;
  {
    struct arg_lookup k;
+ 
    k.name = name;
    k.functions = fns;
    k.classes = NULL_TREE;
! 
!   /* Note that we've already looked at some namespaces during normal
!      unqualified lookup, unless we found a decl in function scope.  */
!   if (fns && ! TREE_PERMANENT (OVL_CURRENT (fns)))
!     k.namespaces = NULL_TREE;
!   else
!     unqualified_namespace_lookup (name, 0, &k.namespaces);
! 
    push_scratch_obstack ();
    arg_assoc_args (&k, args);
    pop_obstacks ();
Index: lex.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/cp/lex.c,v
retrieving revision 1.133
diff -c -p -r1.133 lex.c
*** lex.c	1999/08/11 20:22:26	1.133
--- lex.c	1999/08/14 10:46:43
*************** do_identifier (token, parsing, args)
*** 3078,3087 ****
      id = lastiddecl;
  
    /* Do Koenig lookup if appropriate (inside templates we build lookup
!      expressions instead).  */
    if (args && !current_template_parms && (!id || is_global (id)))
-     /* If we have arguments and we only found global names, do Koenig
-        lookup. */
      id = lookup_arg_dependent (token, id, args);
  
    /* Remember that this name has been used in the class definition, as per
--- 3078,3090 ----
      id = lastiddecl;
  
    /* Do Koenig lookup if appropriate (inside templates we build lookup
!      expressions instead).
! 
!      [basic.lookup.koenig]: If the ordinary unqualified lookup of the name
!      finds the declaration of a class member function, the associated
!      namespaces and classes are not considered.  */
! 
    if (args && !current_template_parms && (!id || is_global (id)))
      id = lookup_arg_dependent (token, id, args);
  
    /* Remember that this name has been used in the class definition, as per
Index: tree.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/cp/tree.c,v
retrieving revision 1.127
diff -c -p -r1.127 tree.c
*** tree.c	1999/08/11 20:22:39	1.127
--- tree.c	1999/08/14 10:46:43
*************** static tree list_hash_lookup PROTO((int,
*** 37,43 ****
  static void propagate_binfo_offsets PROTO((tree, tree));
  static int avoid_overlap PROTO((tree, tree));
  static cp_lvalue_kind lvalue_p_1 PROTO((tree, int));
- static int equal_functions PROTO((tree, tree));
  static tree no_linkage_helper PROTO((tree));
  static tree build_srcloc PROTO((char *, int));
  
--- 37,42 ----
*************** build_overload (decl, chain)
*** 1411,1430 ****
    return ovl_cons (decl, chain);
  }
  
- /* Returns true iff functions are equivalent. Equivalent functions are
-    not identical only if one is a function-local extern function.
-    This assumes that function-locals don't have TREE_PERMANENT.  */
- 
- static int
- equal_functions (fn1, fn2)
-      tree fn1;
-      tree fn2;
- {
-   if (!TREE_PERMANENT (fn1) || !TREE_PERMANENT (fn2))
-     return decls_match (fn1, fn2);
-   return fn1 == fn2;
- }
- 
  /* True if fn is in ovl. */
  
  int
--- 1410,1415 ----
*************** ovl_member (fn, ovl)
*** 1435,1443 ****
    if (ovl == NULL_TREE)
      return 0;
    if (TREE_CODE (ovl) != OVERLOAD)
!     return equal_functions (ovl, fn);
    for (; ovl; ovl = OVL_CHAIN (ovl))
!     if (equal_functions (OVL_FUNCTION (ovl), fn))
        return 1;
    return 0;
  }
--- 1420,1428 ----
    if (ovl == NULL_TREE)
      return 0;
    if (TREE_CODE (ovl) != OVERLOAD)
!     return ovl == fn;
    for (; ovl; ovl = OVL_CHAIN (ovl))
!     if (OVL_FUNCTION (ovl) == fn)
        return 1;
    return 0;
  }


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]