Patchwork [c++] convert keyed_classes to a VEC

login
register
mail settings
Submitter Nathan Froyd
Date Aug. 8, 2010, 5:53 p.m.
Message ID <20100808175324.GA4130@codesourcery.com>
Download mbox | patch
Permalink /patch/61223/
State New
Headers show

Comments

Nathan Froyd - Aug. 8, 2010, 5:53 p.m.
The patch below does just what $SUBJECT says it does.

The patch is not as clean as I'd like, mostly due to the loop in
cp_write_global_declarations.  It would be slightly nicer if we could
iterate over keyed_classes in forward order (i.e. reverse order of how
we accumulated them), but that might not be correct.  A second pair of
eyes would especially be appreciated for that hunk.

Tested on x86_64-unknown-linux-gnu, libstdc++ and g++ testsuites.  OK to
commit?

-Nathan

	* cp-tree.h (enum cp_tree_index) [CPTI_KEYED_CLASSES]: Remove.
	(keyed_classes): Don't define as a macro, but as an extern VEC.
	* class.c (keyed_classes): Define.
	(finish_struct_1): Adjust for type change of keyed_classes.
	* decl.c (record_key_method_defined): Likewise.
	* pt.c (instantiate_class_template): Likewise.
	* decl2.c (cp_write_global_declarations): Likewise.
Mark Mitchell - Aug. 9, 2010, 11:03 a.m.
Nathan Froyd wrote:

> The patch is not as clean as I'd like, mostly due to the loop in
> cp_write_global_declarations.  It would be slightly nicer if we could
> iterate over keyed_classes in forward order (i.e. reverse order of how
> we accumulated them), but that might not be correct. 

Do you mean that you have evidence that it would not be correct, or just
that you're afraid that it might not be correct because you don't feel
you know enough to judge that?

Thanks,
Nathan Froyd - Aug. 9, 2010, 11:12 a.m.
On Mon, Aug 09, 2010 at 12:03:43PM +0100, Mark Mitchell wrote:
> Nathan Froyd wrote:
> > The patch is not as clean as I'd like, mostly due to the loop in
> > cp_write_global_declarations.  It would be slightly nicer if we could
> > iterate over keyed_classes in forward order (i.e. reverse order of how
> > we accumulated them), but that might not be correct. 
> 
> Do you mean that you have evidence that it would not be correct, or just
> that you're afraid that it might not be correct because you don't feel
> you know enough to judge that?

The latter.  I have not tried doing it in forward order; I suppose it
would be reasonable to make the attempt and see what happens.

-Nathan
Mark Mitchell - Aug. 9, 2010, 11:20 a.m.
Nathan Froyd wrote:

>> Do you mean that you have evidence that it would not be correct, or just
>> that you're afraid that it might not be correct because you don't feel
>> you know enough to judge that?
> 
> The latter.  I have not tried doing it in forward order; I suppose it
> would be reasonable to make the attempt and see what happens.

Even the existing code is weirdly ugly.  There are two separate loops
over keyed_classes, but there should really only be one.  Whoever wrote
that code (maybe me?) didn't know about "tree *"; that's the easy way to
iterate through a list when you may need to remove things from the list.

Changing the order of vtable emission is going to change the order of
template instalation for virtual members of template classes.  But, I
don't think the standard has anything to say about order of
instantiation for such functions.  I'd try the obvious forward iteration
 and see what happens.
Jason Merrill - Aug. 16, 2010, 4:21 p.m.
On 08/09/2010 07:20 AM, Mark Mitchell wrote:
> Changing the order of vtable emission is going to change the order of
> template instalation for virtual members of template classes.  But, I
> don't think the standard has anything to say about order of
> instantiation for such functions.  I'd try the obvious forward iteration
>   and see what happens.

Agreed.

Jason

Patch

diff --git a/gcc/cp/class.c b/gcc/cp/class.c
index 73bcb75..6f9d308 100644
--- a/gcc/cp/class.c
+++ b/gcc/cp/class.c
@@ -112,6 +112,10 @@  static GTY (()) tree sizeof_biggest_empty_class;
    declaration order.  */
 VEC(tree,gc) *local_classes;
 
+/* A list of the dynamic classes whose vtables may have to be
+   emitted in this translation unit.  */
+VEC(tree,gc) *keyed_classes;
+
 static tree get_vfield_name (tree);
 static void finish_struct_anon (tree);
 static tree get_vtable_name (tree);
@@ -5450,7 +5454,7 @@  finish_struct_1 (tree t)
       /* If a polymorphic class has no key method, we may emit the vtable
 	 in every translation unit where the class definition appears.  */
       if (CLASSTYPE_KEY_METHOD (t) == NULL_TREE)
-	keyed_classes = tree_cons (NULL_TREE, t, keyed_classes);
+	VEC_safe_push (tree, gc, keyed_classes, t);
     }
 
   /* Layout the class itself.  */
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index baa6656..b669856 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -793,8 +793,6 @@  enum cp_tree_index
     CPTI_DSO_HANDLE,
     CPTI_DCAST,
 
-    CPTI_KEYED_CLASSES,
-
     CPTI_NULLPTR,
     CPTI_NULLPTR_TYPE,
 
@@ -906,11 +904,6 @@  extern GTY(()) tree cp_global_trees[CPTI_MAX];
    destructors.  */
 #define vtt_parm_type			cp_global_trees[CPTI_VTT_PARM_TYPE]
 
-/* A TREE_LIST of the dynamic classes whose vtables may have to be
-   emitted in this translation unit.  */
-
-#define keyed_classes			cp_global_trees[CPTI_KEYED_CLASSES]
-
 /* Node to indicate default access. This must be distinct from the
    access nodes in tree.h.  */
 
@@ -4029,6 +4022,10 @@  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;
+
+/* A list of the dynamic classes whose vtables may have to be
+   emitted in this translation unit.  */
+extern GTY(()) VEC(tree,gc) *keyed_classes;
 
 /* Here's where we control how name mangling takes place.  */
 
diff --git a/gcc/cp/decl.c b/gcc/cp/decl.c
index 4e4a277..5db4215 100644
--- a/gcc/cp/decl.c
+++ b/gcc/cp/decl.c
@@ -12577,7 +12577,7 @@  record_key_method_defined (tree fndecl)
     {
       tree fnclass = DECL_CONTEXT (fndecl);
       if (fndecl == CLASSTYPE_KEY_METHOD (fnclass))
-	keyed_classes = tree_cons (NULL_TREE, fnclass, keyed_classes);
+	VEC_safe_push (tree, gc, keyed_classes, fnclass);
     }
 }
 
diff --git a/gcc/cp/decl2.c b/gcc/cp/decl2.c
index a768877..c3a93ad 100644
--- a/gcc/cp/decl2.c
+++ b/gcc/cp/decl2.c
@@ -3643,30 +3643,38 @@  cp_write_global_declarations (void)
 	 vtables then we remove the class from our list so we don't
 	 have to look at it again.  */
 
-      while (keyed_classes != NULL_TREE
-	     && maybe_emit_vtables (TREE_VALUE (keyed_classes)))
+      while (!VEC_empty (tree, keyed_classes)
+	     && maybe_emit_vtables (VEC_last (tree, keyed_classes)))
 	{
 	  reconsider = true;
-	  keyed_classes = TREE_CHAIN (keyed_classes);
+	  VEC_pop (tree, keyed_classes);
 	}
 
-      t = keyed_classes;
-      if (t != NULL_TREE)
+      /* The last element of the vector (if it exists) has not been
+	 written out.  We still need to iterate through any remaining
+	 members and write them out if necessary.  Do this by
+	 maintaining two indices into the vector: one for the next
+	 candidate to consider and another for the point at which known
+	 unwritten entries start.  */
+
+      if (!VEC_empty (tree, keyed_classes))
 	{
-	  tree next = TREE_CHAIN (t);
+	  int unwritten = VEC_length (tree, keyed_classes) - 1;
+	  int next_idx = unwritten - 1;
 
-	  while (next)
+	  while (next_idx >= 0)
 	    {
-	      if (maybe_emit_vtables (TREE_VALUE (next)))
-		{
-		  reconsider = true;
-		  TREE_CHAIN (t) = TREE_CHAIN (next);
-		}
+	      tree candidate = VEC_index (tree, keyed_classes, next_idx--);
+	      if (maybe_emit_vtables (candidate))
+		reconsider = true;
 	      else
-		t = next;
-
-	      next = TREE_CHAIN (t);
+		/* We didn't write out CANDIDATE.  We need to slide it
+		   to the front of the unwritten entries.  */
+		VEC_replace (tree, keyed_classes, --unwritten, candidate);
 	    }
+
+	  /* All done.  Slide all the unwritten elements down.  */
+	  VEC_block_remove (tree, keyed_classes, 0, unwritten);
 	}
 
       /* Write out needed type info variables.  We have to be careful
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index bb6b1a0..ef9e759 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -8251,7 +8251,7 @@  instantiate_class_template (tree type)
      method, however, finish_struct_1 will already have added TYPE to
      the keyed_classes list.  */
   if (TYPE_CONTAINS_VPTR_P (type) && CLASSTYPE_KEY_METHOD (type))
-    keyed_classes = tree_cons (NULL_TREE, type, keyed_classes);
+    VEC_safe_push (tree, gc, keyed_classes, type);
 
   return type;
 }