C++ PATCH to avoid duplicate overload resolution (related to c++/48481)

C++ PATCH to avoid duplicate overload resolution (related to c++/48481)

[Jason Merrill]

[-- Attachment #1: Type: text/plain, Size: 530 bytes --]

While I was looking at 48481 a while back, I noticed that since Doug's 
change to implement DR 164, in a call subject to argument-dependent 
lookup we end up considering every function twice.  This patch avoids 
this by using a pointer set to remember which functions we already have 
in the overload set.  It cuts the compilation time for cases of extreme 
overloading (such as the 48481 testcase) by almost 50%, and has no 
noticeable effect on more normal code such as stdc++.h.

Tested x86_64-pc-linux-gnu, applying to trunk.

[-- Attachment #2: 48481-3.patch --]
[-- Type: text/x-patch, Size: 4900 bytes --]

commit c501c0ce3b749925475b8d3be0bc52843d37504d
Author: Jason Merrill <jason@redhat.com>
Date:   Thu Jun 30 00:03:40 2011 -0400

    	PR c++/48481
    	* name-lookup.c (struct arg_lookup): Add fn_set.
    	(add_function): Check it.
    	(lookup_arg_dependent_1): Initialize it.

diff --git a/gcc/cp/name-lookup.c b/gcc/cp/name-lookup.c
index 8bf5f5f..615e177 100644
--- a/gcc/cp/name-lookup.c
+++ b/gcc/cp/name-lookup.c
@@ -33,6 +33,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "debug.h"
 #include "c-family/c-pragma.h"
 #include "params.h"
+#include "pointer-set.h"
 
 /* The bindings for a particular name in a particular scope.  */
 
@@ -4864,6 +4865,7 @@ struct arg_lookup
   VEC(tree,gc) *namespaces;
   VEC(tree,gc) *classes;
   tree functions;
+  struct pointer_set_t *fn_set;
 };
 
 static bool arg_assoc (struct arg_lookup*, tree);
@@ -4883,16 +4885,11 @@ static bool arg_assoc_template_arg (struct arg_lookup*, tree);
 static bool
 add_function (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.  In doing this, we
-     assume that the number of duplicates will be small compared to the
-     total number of functions being compared, which should usually be the
-     case.  */
-
   if (!is_overloaded_fn (fn))
     /* All names except those of (possibly overloaded) functions and
        function templates are ignored.  */;
+  else if (k->fn_set && pointer_set_insert (k->fn_set, fn))
+    /* It's already in the list.  */;
   else if (!k->functions)
     k->functions = fn;
   else if (fn == k->functions)
@@ -5346,6 +5343,23 @@ lookup_arg_dependent_1 (tree name, tree fns, VEC(tree,gc) *args,
      picking up later definitions) in the second stage. */
   k.namespaces = make_tree_vector ();
 
+  /* We used to allow duplicates and let joust discard them, but
+     since the above change for DR 164 we end up with duplicates of
+     all the functions found by unqualified lookup.  So keep track
+     of which ones we've seen.  */
+  if (fns)
+    {
+      tree ovl;
+      /* We shouldn't be here if lookup found something other than
+	 namespace-scope functions.  */
+      gcc_assert (DECL_NAMESPACE_SCOPE_P (OVL_CURRENT (fns)));
+      k.fn_set = pointer_set_create ();
+      for (ovl = fns; ovl; ovl = OVL_NEXT (ovl))
+	pointer_set_insert (k.fn_set, OVL_CURRENT (ovl));
+    }
+  else
+    k.fn_set = NULL;
+
   if (include_std)
     arg_assoc_namespace (&k, std_node);
   arg_assoc_args_vec (&k, args);
@@ -5363,6 +5377,8 @@ lookup_arg_dependent_1 (tree name, tree fns, VEC(tree,gc) *args,
 
   release_tree_vector (k.classes);
   release_tree_vector (k.namespaces);
+  if (k.fn_set)
+    pointer_set_destroy (k.fn_set);
     
   return fns;
 }
diff --git a/gcc/testsuite/g++.dg/template/crash37.C b/gcc/testsuite/g++.dg/template/crash37.C
index 6072423..d5167c8 100644
--- a/gcc/testsuite/g++.dg/template/crash37.C
+++ b/gcc/testsuite/g++.dg/template/crash37.C
@@ -11,7 +11,7 @@ struct coperator_stack
 struct helper {};
 
 template<class F>
-void bla(F f) // { dg-message "bla|no known conversion" }
+void bla(F f)
 {
 }
 
@@ -20,8 +20,7 @@ struct definition
 {
  definition()
  {
-   bla(coperator_stack::push3<helper>); // { dg-error "matching" }
-   // { dg-message "candidate" "candidate note" { target *-*-* } 23 }
+   bla(coperator_stack::push3<helper>); // { dg-error "pointer to member" }
  }
 };
 
diff --git a/gcc/testsuite/g++.dg/template/ptrmem4.C b/gcc/testsuite/g++.dg/template/ptrmem4.C
index 62262c4..14f36d4 100644
--- a/gcc/testsuite/g++.dg/template/ptrmem4.C
+++ b/gcc/testsuite/g++.dg/template/ptrmem4.C
@@ -16,6 +16,5 @@ struct SpyExample
 
 void SpyExample::ready()
 {
-  queryAliases(inputs); // { dg-error "matching" }
-  // { dg-message "candidate" "candidate note" { target *-*-* } 19 }
+  queryAliases(inputs); // { dg-error "matching|unresolved" }
 }
diff --git a/gcc/testsuite/g++.old-deja/g++.other/pmf3.C b/gcc/testsuite/g++.old-deja/g++.other/pmf3.C
index 11e648e..448d791 100644
--- a/gcc/testsuite/g++.old-deja/g++.other/pmf3.C
+++ b/gcc/testsuite/g++.old-deja/g++.other/pmf3.C
@@ -3,7 +3,7 @@
 // Bug: g++ was crashing after giving errors.
 
 template<class T>
-  void connect_to_method( // { dg-message "connect_to_method|no known conversion" }
+  void connect_to_method(
     T *receiver,
     void (T::*method)())
   {}
@@ -20,7 +20,6 @@ public:
 
 Gtk_Base::Gtk_Base()
 {
-  connect_to_method(this,&show);   // { dg-error "no match" } invalid pmf expression
-  // { dg-message "candidate" "candidate note" { target *-*-* } 23 }
+  connect_to_method(this,&show);   // { dg-error "pointer to member" } invalid pmf expression
   connect_to_method(this,&expose); // { dg-error "pointer to member" } invalid pmf expression
 }

Re: C++ PATCH to avoid duplicate overload resolution (related to c++/48481)

[Jakub Jelinek]

On Thu, Jun 30, 2011 at 05:08:49PM -0400, Jason Merrill wrote:
> Author: Jason Merrill <jason@redhat.com>
> Date:   Thu Jun 30 00:03:40 2011 -0400
> 
>     	PR c++/48481
>     	* name-lookup.c (struct arg_lookup): Add fn_set.
>     	(add_function): Check it.
>     	(lookup_arg_dependent_1): Initialize it.
> 
> diff --git a/gcc/cp/name-lookup.c b/gcc/cp/name-lookup.c
> index 8bf5f5f..615e177 100644
> --- a/gcc/cp/name-lookup.c
> +++ b/gcc/cp/name-lookup.c
> @@ -33,6 +33,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "debug.h"
>  #include "c-family/c-pragma.h"
>  #include "params.h"
> +#include "pointer-set.h"

Then cp/name-lookup.o should depend on pointer-set.h in cp/Make-lang.in.
Fixed thusly, so far untested, I've noticed a couple of other spots.  Ok for
trunk after testing?

OT, if we don't switch to on the fly dependency generation, I think it would
be nice to at least a write a maintainer-script that would regenerate GCC
style rules for dependences in Makefile.in and */Make-lang.in -
dependencies on just immediately mentioned headers, and for headers
with dependencies find a matching SPLAY_TREE_H etc. variable, which we
could run once a month or so to make sure our Makefiles are up to date.

2011-07-01  Jakub Jelinek  <jakub@redhat.com>

	* Make-lang.in (cp/decl.o): Depend on pointer-set.h.
	(cp/class.o): Likewise.
	(cp/error.o): Likewise.
	(cp/name-lookup.o): Likewise.
	(cp/decl2.o): Likewise.  Don't depend on $(POINTER_SET_H).

--- gcc/cp/Make-lang.in.jj	2011-06-17 11:01:54.000000000 +0200
+++ gcc/cp/Make-lang.in	2011-07-01 09:19:29.000000000 +0200
@@ -266,11 +266,11 @@ cp/decl.o: cp/decl.c $(CXX_TREE_H) $(TM_
   output.h toplev.h $(HASHTAB_H) $(RTL_H) \
   cp/operators.def $(TM_P_H) $(TREE_INLINE_H) $(DIAGNOSTIC_H) $(C_PRAGMA_H) \
   debug.h gt-cp-decl.h $(TIMEVAR_H) $(TARGET_H) $(PLUGIN_H) \
-  intl.h tree-iterator.h $(SPLAY_TREE_H) \
+  intl.h tree-iterator.h pointer-set.h $(SPLAY_TREE_H) \
   c-family/c-objc.h
 cp/decl2.o: cp/decl2.c $(CXX_TREE_H) $(TM_H) $(FLAGS_H) cp/decl.h \
   output.h toplev.h $(C_COMMON_H) gt-cp-decl2.h $(CGRAPH_H) \
-  $(C_PRAGMA_H) $(TREE_DUMP_H) intl.h $(TARGET_H) $(GIMPLE_H) $(POINTER_SET_H) \
+  $(C_PRAGMA_H) $(TREE_DUMP_H) intl.h $(TARGET_H) $(GIMPLE_H) pointer-set.h \
   $(SPLAY_TREE_H) c-family/c-ada-spec.h \
   c-family/c-objc.h
 cp/cp-objcp-common.o : cp/cp-objcp-common.c $(CONFIG_H) $(SYSTEM_H) \
@@ -284,7 +284,7 @@ cp/typeck.o: cp/typeck.c $(CXX_TREE_H) $
   output.h c-family/c-objc.h
 cp/class.o: cp/class.c $(CXX_TREE_H) $(TM_H) $(FLAGS_H) toplev.h \
   $(TARGET_H) convert.h $(CGRAPH_H) $(TREE_DUMP_H) gt-cp-class.h \
-  $(SPLAY_TREE_H)
+  $(SPLAY_TREE_H) pointer-set.h
 cp/call.o: cp/call.c $(CXX_TREE_H) $(TM_H) $(FLAGS_H) toplev.h \
   $(DIAGNOSTIC_CORE_H) intl.h gt-cp-call.h convert.h $(TARGET_H) langhooks.h \
   $(TIMEVAR_H) c-family/c-objc.h
@@ -312,7 +312,7 @@ cp/pt.o: cp/pt.c $(CXX_TREE_H) $(TM_H) c
   c-family/c-objc.h
 cp/error.o: cp/error.c $(CXX_TREE_H) $(TM_H) $(DIAGNOSTIC_H) \
   $(FLAGS_H) $(REAL_H) $(LANGHOOKS_DEF_H) $(CXX_PRETTY_PRINT_H) \
-  tree-diagnostic.h tree-pretty-print.h c-family/c-objc.h
+  tree-diagnostic.h tree-pretty-print.h pointer-set.h c-family/c-objc.h
 cp/repo.o: cp/repo.c $(CXX_TREE_H) $(TM_H) toplev.h $(DIAGNOSTIC_CORE_H) \
   gt-cp-repo.h
 cp/semantics.o: cp/semantics.c $(CXX_TREE_H) $(TM_H) toplev.h \
@@ -333,7 +333,7 @@ cp/cp-gimplify.o: cp/cp-gimplify.c $(CXX
 
 cp/name-lookup.o: cp/name-lookup.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
 	$(TM_H) $(CXX_TREE_H) $(TIMEVAR_H) gt-cp-name-lookup.h \
-	$(DIAGNOSTIC_CORE_H) $(FLAGS_H) debug.h
+	$(DIAGNOSTIC_CORE_H) $(FLAGS_H) debug.h pointer-set.h
 
 cp/cxx-pretty-print.o: cp/cxx-pretty-print.c $(CXX_PRETTY_PRINT_H) \
   $(CONFIG_H) $(SYSTEM_H) $(TM_H) coretypes.h $(CXX_TREE_H) tree-pretty-print.h


	Jakub

Re: C++ PATCH to avoid duplicate overload resolution (related to c++/48481)

[Joseph S. Myers]

On Fri, 1 Jul 2011, Jakub Jelinek wrote:

> OT, if we don't switch to on the fly dependency generation, I think it would
> be nice to at least a write a maintainer-script that would regenerate GCC
> style rules for dependences in Makefile.in and */Make-lang.in -

(and in config/*/t-*)

> dependencies on just immediately mentioned headers, and for headers
> with dependencies find a matching SPLAY_TREE_H etc. variable, which we
> could run once a month or so to make sure our Makefiles are up to date.

I commented a bit on dependency generation at 
<http://gcc.gnu.org/ml/gcc-patches/2011-05/msg01925.html> - I think the 
incremental approach I suggested there is more likely to make useful 
progress than trying to do it again with a monolithic patch.  Various 
cleanups would also be helpful for both automatic generation and 
maintainer-script updates of dependencies.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: C++ PATCH to avoid duplicate overload resolution (related to c++/48481)

[Jason Merrill]

OK, thanks.

Jason