[C++] Fix PR90801

Message ID alpine.LSU.2.20.1906111158030.10704@zhemvz.fhfr.qr
State New
Headers show
Series
  • [C++] Fix PR90801
Related show

Commit Message

Richard Biener June 11, 2019, 10:45 a.m.
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.

Comments

Jason Merrill June 11, 2019, 1:58 p.m. | #1
On Tue, Jun 11, 2019, 6:45 AM Richard Biener <rguenther@suse.de> wrote:

>

> 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?

>


Ok, thanks.

Jason


> 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:

>
Richard Biener June 12, 2019, 11:07 a.m. | #2
On Tue, 11 Jun 2019, Jason Merrill wrote:

> On Tue, Jun 11, 2019, 6:45 AM Richard Biener <rguenther@suse.de> wrote:

> 

> >

> > 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?

> >

> 

> Ok, thanks.


Installed.

Below is the simplest variant re-adding optimized handling
of single-element removal.  Note the second hunk which
moves the num_split_elts increment so it doesn't happen
when split_nonconstant_init_1 returns false.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

OK?

Richard.

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

	PR c++/90801
	* typeck2.c (split_nonconstant_init_1): Properly count
	num_split_elts, optimize single constructor elt removal.

Index: gcc/cp/typeck2.c
===================================================================
--- gcc/cp/typeck2.c	(revision 272177)
+++ 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, tidx;
+  unsigned HOST_WIDE_INT idx, tidx = HOST_WIDE_INT_M1U;
   tree field_index, value;
   tree type = TREE_TYPE (dest);
   tree inner_type = NULL;
@@ -657,9 +657,13 @@ split_nonconstant_init_1 (tree dest, tre
 	      if (!split_nonconstant_init_1 (sub, value))
 		complete_p = false;
 	      else
-		/* Mark element for removal.  */
-		CONSTRUCTOR_ELT (init, idx)->index = NULL_TREE;
-	      num_split_elts++;
+		{
+		  /* Mark element for removal.  */
+		  CONSTRUCTOR_ELT (init, idx)->index = NULL_TREE;
+		  if (idx < tidx)
+		    tidx = idx;
+		  num_split_elts++;
+		}
 	    }
 	  else if (!initializer_constant_valid_p (value, inner_type))
 	    {
@@ -668,6 +672,8 @@ split_nonconstant_init_1 (tree dest, tre
 
 	      /* Mark element for removal.  */
 	      CONSTRUCTOR_ELT (init, idx)->index = NULL_TREE;
+	      if (idx < tidx)
+		tidx = idx;
 
 	      if (TREE_CODE (field_index) == RANGE_EXPR)
 		{
@@ -705,17 +711,18 @@ split_nonconstant_init_1 (tree dest, tre
 	      num_split_elts++;
 	    }
 	}
-      if (num_split_elts != 0)
+      if (num_split_elts == 1)
+	CONSTRUCTOR_ELTS (init)->ordered_remove (tidx);
+      else if (num_split_elts > 1)
 	{
 	  /* Perform the delayed ordered removal of non-constant elements
 	     we split out.  */
-	  for (tidx = 0, idx = 0; idx < CONSTRUCTOR_NELTS (init); ++idx)
+	  for (idx = tidx; 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);
+		*CONSTRUCTOR_ELT (init, tidx) = *CONSTRUCTOR_ELT (init, idx);
 		++tidx;
 	      }
 	  vec_safe_truncate (CONSTRUCTOR_ELTS (init), tidx);
Jason Merrill June 12, 2019, 9:34 p.m. | #3
On 6/12/19 7:07 AM, Richard Biener wrote:
> On Tue, 11 Jun 2019, Jason Merrill wrote:

> 

>> On Tue, Jun 11, 2019, 6:45 AM Richard Biener <rguenther@suse.de> wrote:

>>

>>>

>>> 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?

>>>

>>

>> Ok, thanks.

> 

> Installed.

> 

> Below is the simplest variant re-adding optimized handling

> of single-element removal.  Note the second hunk which

> moves the num_split_elts increment so it doesn't happen

> when split_nonconstant_init_1 returns false.

> 

> Bootstrapped and tested on x86_64-unknown-linux-gnu.

> 

> OK?


OK.

Jason

Patch

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: