[pph] Fix method lookups (part 1)

[Diego Novillo, 2011-09-09 20:37:20]

The main problem fixed here is that name lookups for class methods
uses a binary search that assumes that the methods in
CLASSTYPE_METHOD_VEC are sorted by pointer value.

Since the reader typically allocates trees in a different pattern than
the writer, it is common for the symbols in the vector to have
different pointer values, so the order used by the writer is different
than the reader.

This was causing us to fail name lookups when generating the pph image
for x6dynarray5.h and x6dynarray6.h.

To fix this, I am making finish_struct_methods an extern function and
calling it after reading a type that has a CLASSTYPE_METHOD_VEC.

This exposed another failure that was simple enough to roll in
together with this patch.  We should not emit preloaded symbols when
writing the names in the global namespace.  This was causing a
DECL_CHAIN cycle.  I added a new filter PPHF_NO_PREFS to skip the
preloaded symbols when needed.

There is another failure exposed by this patch that I am going to fix
separately.  It goes something like this:

File decl.h:
---------------------------------------------------------------------------
class X
{
    void foo(int);
};
---------------------------------------------------------------------------

File impl.h:
---------------------------------------------------------------------------
#include "decl.h"
void X::foo(int x) { return x + 1; }
---------------------------------------------------------------------------
  
We generate pph images for decl.h and impl.h.  The problem begins when
we are generating impl.pph.  When the time comes to write impl.pph's
symbol table we go to write X::foo() and find it inside the pickle
cache of decl.pph (since we are including it).  So, instead of
pickling it again, we write an external reference to the pickled
representation in decl.pph.

The problem here is that the pickled representation in decl.pph
contains the DECLARATION for X::foo().  When we parsed impl.h, we
overwrote the DECL node to convert it into the IMPLEMENTATION of
X::foo().

So, when reading impl.pph from a translation unit, we never read the
implementation for X::foo, which confuses the compiler and produces an
ICE.

I will implement a way of detecting and replaying these in-place
modifications in my next patch.

Tested on x86_64.  Committed to pph.


Diego.

cp/ChangeLog.pph

	* class.c (finish_struct_methods): Make extern.
	* cp-tree.h (finish_struct_methdods): Declare.
	* pph-streamer-in.c (pph_in_tcc_type): Call it.
	* pph-streamer.h (PPHF_NO_PREFS): Define.
	* pph-streamer-out.c (pph_tree_matches): Use it to filter trees
	present in the preloaded cache.
	(pph_out_scope_chain): Call pph_out_binding_level_1 with
	PPH_NO_PREFS in the filter.

testsuite/ChangeLog.pph

	* g++.dg/pph/x6dynarray3.cc: Change failure from ICE to asm diff.
	* g++.dg/pph/x6dynarray4.cc: Change expected failure.
	* g++.dg/pph/x6dynarray5.h: Mark fixed.
	* g++.dg/pph/x6dynarray6.h: Mark fixed.
	* g++.dg/pph/x7dynarray5.cc: Change expected failure.

diff --git a/gcc/cp/class.c b/gcc/cp/class.c
index 4e3a58f..0a63c78 100644
--- a/gcc/cp/class.c
+++ b/gcc/cp/class.c
@@ -127,7 +127,6 @@ static void handle_using_decl (tree, tree);
 static tree dfs_modify_vtables (tree, void *);
 static tree modify_all_vtables (tree, tree);
 static void determine_primary_bases (tree);
-static void finish_struct_methods (tree);
 static void maybe_warn_about_overly_private_class (tree);
 static int method_name_cmp (const void *, const void *);
 static int resort_method_name_cmp (const void *, const void *);
@@ -1793,7 +1792,7 @@ resort_type_method_vec (void* obj,
    and type conversion operators) so that we can find them faster in
    search.  */
 
-static void
+void
 finish_struct_methods (tree t)
 {
   tree fn_fields;
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 3da77a7..6cd52aa 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -4117,6 +4117,8 @@ extern int current_class_depth;
 /* An array of all local classes present in this translation unit, in
    declaration order.  */
 extern GTY(()) VEC(tree,gc) *local_classes;
+
+void finish_struct_methods (tree);
 
 /* Here's where we control how name mangling takes place.  */
 
diff --git a/gcc/cp/pph-streamer-in.c b/gcc/cp/pph-streamer-in.c
index 2fcb436..b111850 100644
--- a/gcc/cp/pph-streamer-in.c
+++ b/gcc/cp/pph-streamer-in.c
@@ -1750,6 +1750,15 @@ pph_in_tcc_type (pph_stream *stream, tree type)
     default:
       break;
     }
+
+  /* If TYPE has a METHOD_VEC, we need to resort it.  Name lookup in
+     classes relies on the specific ordering of the class method
+     pointers.  Since we generally instantiate them in a different
+     order than the original compile, the pointer values will be
+     different.  This will cause name lookups to fail, unless we
+     resort the vector.  */
+  if (TYPE_LANG_SPECIFIC (type) && CLASSTYPE_METHOD_VEC (type))
+    finish_struct_methods (type);
 }
 
 
diff --git a/gcc/cp/pph-streamer-out.c b/gcc/cp/pph-streamer-out.c
index 27495e7..264294c 100644
--- a/gcc/cp/pph-streamer-out.c
+++ b/gcc/cp/pph-streamer-out.c
@@ -369,6 +369,10 @@ pph_tree_matches (tree t, unsigned filter)
       && DECL_IS_BUILTIN (t))
     return false;
 
+  if ((filter & PPHF_NO_PREFS)
+      && pph_cache_lookup (NULL, t, NULL))
+    return false;
+
   if ((filter & PPHF_NO_XREFS)
       && pph_cache_lookup_in_includes (t, NULL, NULL))
     return false;
@@ -1044,7 +1048,8 @@ pph_out_scope_chain (pph_stream *stream)
     pph_cache_add (&stream->cache, scope_chain->bindings, &ix);
     pph_out_record_marker (stream, PPH_RECORD_START);
     pph_out_uint (stream, ix);
-    pph_out_binding_level_1 (stream, scope_chain->bindings, PPHF_NO_XREFS);
+    pph_out_binding_level_1 (stream, scope_chain->bindings,
+			     PPHF_NO_XREFS | PPHF_NO_PREFS);
   }
 }
 
diff --git a/gcc/cp/pph-streamer.h b/gcc/cp/pph-streamer.h
index cc841eb..7205d64 100644
--- a/gcc/cp/pph-streamer.h
+++ b/gcc/cp/pph-streamer.h
@@ -229,6 +229,7 @@ typedef struct pph_stream {
 #define PPHF_NONE		0
 #define PPHF_NO_BUILTINS	(1 << 0)
 #define PPHF_NO_XREFS		(1 << 1)
+#define PPHF_NO_PREFS		(1 << 2)
 
 /* In pph-streamer.c.  */
 void pph_init_preloaded_cache (void);
diff --git a/gcc/testsuite/g++.dg/pph/x6dynarray3.cc
b/gcc/testsuite/g++.dg/pph/x6dynarray3.cc
index f767c14..c600ce0 100644
--- a/gcc/testsuite/g++.dg/pph/x6dynarray3.cc
+++ b/gcc/testsuite/g++.dg/pph/x6dynarray3.cc
@@ -1,6 +1,5 @@
-// { dg-xfail-if "ICE" { "*-*-*" } { "-fpph-map=pph.map" } }
-// { dg-bogus "x6dynarray3.cc:1:0: internal compiler error: in chainon, at
tree.c" "" { xfail *-*-* } 0 }
-
+// pph asm xdiff 30893
+// .Lnn labels emitted with different values of 'nn'.
 #include "x5dynarray3.h"
 
 #include "a0integer.h"
diff --git a/gcc/testsuite/g++.dg/pph/x6dynarray4.cc
b/gcc/testsuite/g++.dg/pph/x6dynarray4.cc
index 3c16683..2dfd24b 100644
--- a/gcc/testsuite/g++.dg/pph/x6dynarray4.cc
+++ b/gcc/testsuite/g++.dg/pph/x6dynarray4.cc
@@ -1,6 +1,5 @@
 // { dg-xfail-if "BOGUS" { "*-*-*" } { "-fpph-map=pph.map" } }
-// { dg-bogus "error: Cannot open PPH file for reading: x6dynarray5.pph: No
such file or directory" "" { xfail *-*-* } 0 }
-
+// { dg-bogus "internal compiler error: Segmentation fault" "" { xfail *-*-* }
0 }
 #include "x6dynarray5.h"
 
 #include <algorithm>
diff --git a/gcc/testsuite/g++.dg/pph/x6dynarray5.h
b/gcc/testsuite/g++.dg/pph/x6dynarray5.h
index e9e379e..69dbcb8 100644
--- a/gcc/testsuite/g++.dg/pph/x6dynarray5.h
+++ b/gcc/testsuite/g++.dg/pph/x6dynarray5.h
@@ -1,7 +1,3 @@
-// { dg-xfail-if "BOGUS" { "*-*-*" } { "-fpph-map=pph.map" } }
-// { dg-bogus "a0dynarray-dfn1b.hi:3:19: error: there are no arguments to
'alloc' that depend on a template parameter, so a declaration of 'alloc' must be
available" "" { xfail *-*-* } 0 }
-// { dg-bogus "a0dynarray-dfn3b.hi:2:36: error: no 'void
tst::dynarray<T>::check.tst::dynarray<T>::size_type.' member function declared
in class 'tst::dynarray<T>'" "" { xfail *-*-* } 0 }
-
 #ifndef X6DYNARRAY5_H
 #define X6DYNARRAY5_H
 
diff --git a/gcc/testsuite/g++.dg/pph/x6dynarray6.h
b/gcc/testsuite/g++.dg/pph/x6dynarray6.h
index 497eb46..3e9d8d4 100644
--- a/gcc/testsuite/g++.dg/pph/x6dynarray6.h
+++ b/gcc/testsuite/g++.dg/pph/x6dynarray6.h
@@ -1,7 +1,5 @@
 // { dg-xfail-if "BOGUS" { "*-*-*" } { "-fpph-map=pph.map" } }
 // { dg-bogus "wchar.h:1:0: error: PPH file stdio.pph fails macro validation,
_WCHAR_H" "" { xfail *-*-* } 0 }
-// { dg-bogus "a0dynarray-dfn1b.hi:3:19: error: there are no arguments to
.alloc. that depend on a template parameter, so a declaration of .alloc. must be
available" "" { xfail *-*-* } 0 }
-// { dg-bogus "a0dynarray-dfn3c.hi:2:36: error: no .void
tst::dynarray<T>::check.tst::dynarray<T>::size_type.. member function declared
in class .tst::dynarray<T>." "" { xfail *-*-* } 0 }
 
 #ifndef X6DYNARRAY6_H
 #define X6DYNARRAY6_H
diff --git a/gcc/testsuite/g++.dg/pph/x7dynarray5.cc
b/gcc/testsuite/g++.dg/pph/x7dynarray5.cc
index d7b17a3..045b0bb 100644
--- a/gcc/testsuite/g++.dg/pph/x7dynarray5.cc
+++ b/gcc/testsuite/g++.dg/pph/x7dynarray5.cc
@@ -1,5 +1,5 @@
 // { dg-xfail-if "BOGUS" { "*-*-*" } { "-fpph-map=pph.map" } }
-// { dg-bogus "wchar.h:1:0: error: PPH file stdio.pph fails macro validation,
_WCHAR_H" "" { xfail *-*-* } 0 }
+// { dg-bogus "internal compiler error: Segmentation fault" "" { xfail *-*-* }
0 }
 
 #include "x0dynarray4.h"
 #include "x6dynarray5.h"

--
This patch is available for review at http://codereview.appspot.com/4997042

[gcharette1, 2011-09-10 15:30:38]

On Fri, Sep 9, 2011 at 4:37 PM, Diego Novillo <dnovillo@google.com> wrote:
>
> The main problem fixed here is that name lookups for class methods
> uses a binary search that assumes that the methods in
> CLASSTYPE_METHOD_VEC are sorted by pointer value.
>
> Since the reader typically allocates trees in a different pattern than
> the writer, it is common for the symbols in the vector to have
> different pointer values, so the order used by the writer is different
> than the reader.
>
> This was causing us to fail name lookups when generating the pph image
> for x6dynarray5.h and x6dynarray6.h.
>
> To fix this, I am making finish_struct_methods an extern function and
> calling it after reading a type that has a CLASSTYPE_METHOD_VEC.
>
> This exposed another failure that was simple enough to roll in
> together with this patch.  We should not emit preloaded symbols when
> writing the names in the global namespace.  This was causing a
> DECL_CHAIN cycle.  I added a new filter PPHF_NO_PREFS to skip the
> preloaded symbols when needed.
>

The loop in the DECL_CHAIN in x6dynarray5 was already there before.
This is why I had introduced the preloaded cache to do something along
those lines.

However I don't think simply filtering it out is sufficient in this
case. The reason there is a loop in this case if I recall correctly is
that "new" (amongst others) is overloaded in #include <new>. i.e. it
used to be filtered by PPHF_NO_BUILTINS, but the overload clears the
BUILTIN_LOCATION and thus the builtins filter doesn't filter new out
anymore (but the pointer itself didn't change, so yes filtering PREFs
WILL filter it out, but it will also ignore the overload and load the
old PREF on the way in, not the new "new" overloaded by the include).

By not filtering it out however we create a loop: as, since the
pointer itself hasn't changed, we output the PREF (because we get a
preloaded cache hit), so either way we loose the overload and if not
filtering it out create a loop on the way in, but what we really need
is to output the overload and correctly re-push_overloaded_decl (or
something that has the same effect) on the way in.

Anyways, just can't help it, but keep reading all the patches coming in :)!

Cheers,
Gab

[Diego Novillo, 2011-09-12 12:06:57]

On Sat, Sep 10, 2011 at 11:30, Gabriel Charette <gcharette1@gmail.com> wrote:
> On Fri, Sep 9, 2011 at 4:37 PM, Diego Novillo <dnovillo@google.com> wrote:
>>
>> The main problem fixed here is that name lookups for class methods
>> uses a binary search that assumes that the methods in
>> CLASSTYPE_METHOD_VEC are sorted by pointer value.
>>
>> Since the reader typically allocates trees in a different pattern than
>> the writer, it is common for the symbols in the vector to have
>> different pointer values, so the order used by the writer is different
>> than the reader.
>>
>> This was causing us to fail name lookups when generating the pph image
>> for x6dynarray5.h and x6dynarray6.h.
>>
>> To fix this, I am making finish_struct_methods an extern function and
>> calling it after reading a type that has a CLASSTYPE_METHOD_VEC.
>>
>> This exposed another failure that was simple enough to roll in
>> together with this patch.  We should not emit preloaded symbols when
>> writing the names in the global namespace.  This was causing a
>> DECL_CHAIN cycle.  I added a new filter PPHF_NO_PREFS to skip the
>> preloaded symbols when needed.
>>
>
> The loop in the DECL_CHAIN in x6dynarray5 was already there before.
> This is why I had introduced the preloaded cache to do something along
> those lines.
>
> However I don't think simply filtering it out is sufficient in this
> case.

It is for this case.  But you are right that it isn't for state
mutations like the one you describe later.  I'm trying to fix this by
detecting state changes between read-time and write-time.  I'm
thinking of checksumming the input tree and create a merge record when
we notice that the tree has mutated during write.  We would only
checksum the input when generating PPH images, so this would never
slow down the reader.

> Anyways, just can't help it, but keep reading all the patches coming in :)!

Heh.  I can send you the copyright assignments for you to fill out.
Don't think you can escape so easily ;)


Diego.