[PATCH][C++] Fix PR90801

Jason Merrill jason@redhat.com
Tue Jun 11 13:58:00 GMT 2019


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



More information about the Gcc-patches mailing list