On Tue, Jun 11, 2019, 6:45 AM Richard Biener <rguent...@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 <rguent...@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:
>
