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