[PATCH][C++] Fix PR90801

Richard Biener rguenther@suse.de
Tue Jun 11 10:45:00 GMT 2019


The following fixes the documented(!) quadraticness in
split_nonconstant_init_1 by simply marking to be removed
constructor elements and doing that in a second run over
the constructor.

More micro-optimizing would be possible by recording the
first removed element index and special-casing removing
of a single element.  If you think that's worth the extra
complexity I can work on that (hopefully the case we
increase num_split_elts but not actually split is a bug...).

Bootstrap / regtest running on x86_64-unknown-linux-gnu.

OK if that passes?

Thanks,
Richard.

2019-06-11  Richard Biener  <rguenther@suse.de>

	PR c++/90801
	* typeck2.c (split_nonconstant_init_1): Avoid ordered remove
	from CONSTRUCTOR by marking to remove elements and doing all
	of them in a O(n) scan.

Index: gcc/cp/typeck2.c
===================================================================
--- gcc/cp/typeck2.c	(revision 272147)
+++ gcc/cp/typeck2.c	(working copy)
@@ -603,7 +603,7 @@ cxx_incomplete_type_error (location_t lo
 static bool
 split_nonconstant_init_1 (tree dest, tree init)
 {
-  unsigned HOST_WIDE_INT idx;
+  unsigned HOST_WIDE_INT idx, tidx;
   tree field_index, value;
   tree type = TREE_TYPE (dest);
   tree inner_type = NULL;
@@ -657,7 +657,8 @@ split_nonconstant_init_1 (tree dest, tre
 	      if (!split_nonconstant_init_1 (sub, value))
 		complete_p = false;
 	      else
-		CONSTRUCTOR_ELTS (init)->ordered_remove (idx--);
+		/* Mark element for removal.  */
+		CONSTRUCTOR_ELT (init, idx)->index = NULL_TREE;
 	      num_split_elts++;
 	    }
 	  else if (!initializer_constant_valid_p (value, inner_type))
@@ -665,15 +666,8 @@ split_nonconstant_init_1 (tree dest, tre
 	      tree code;
 	      tree sub;
 
-	      /* FIXME: Ordered removal is O(1) so the whole function is
-		 worst-case quadratic. This could be fixed using an aside
-		 bitmap to record which elements must be removed and remove
-		 them all at the same time. Or by merging
-		 split_non_constant_init into process_init_constructor_array,
-		 that is separating constants from non-constants while building
-		 the vector.  */
-	      CONSTRUCTOR_ELTS (init)->ordered_remove (idx);
-	      --idx;
+	      /* Mark element for removal.  */
+	      CONSTRUCTOR_ELT (init, idx)->index = NULL_TREE;
 
 	      if (TREE_CODE (field_index) == RANGE_EXPR)
 		{
@@ -711,6 +705,21 @@ split_nonconstant_init_1 (tree dest, tre
 	      num_split_elts++;
 	    }
 	}
+      if (num_split_elts != 0)
+	{
+	  /* Perform the delayed ordered removal of non-constant elements
+	     we split out.  */
+	  for (tidx = 0, idx = 0; idx < CONSTRUCTOR_NELTS (init); ++idx)
+	    if (CONSTRUCTOR_ELT (init, idx)->index == NULL_TREE)
+	      ;
+	    else
+	      {
+		if (tidx != idx)
+		  *CONSTRUCTOR_ELT (init, tidx) = *CONSTRUCTOR_ELT (init, idx);
+		++tidx;
+	      }
+	  vec_safe_truncate (CONSTRUCTOR_ELTS (init), tidx);
+	}
       break;
 
     case VECTOR_TYPE:



More information about the Gcc-patches mailing list