From ceaaf873e9392ac3f196c400afbc91f70a9dbce2 Mon Sep 17 00:00:00 2001 From: Jason Merrill Date: Mon, 17 Aug 2015 14:42:04 -0400 Subject: [PATCH] re PR c++/67104 (Constant expression factory function initializes std::array with static storage duration strangely) PR c++/67104 * constexpr.c (array_index_cmp, find_array_ctor_elt): New. (cxx_eval_array_reference, cxx_eval_store_expression): Use them. From-SVN: r226949 --- gcc/cp/ChangeLog | 4 ++ gcc/cp/constexpr.c | 171 +++++++++++++++++++++++++++++++++------------ 2 files changed, 129 insertions(+), 46 deletions(-) diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog index c6bd397748a..078ee74f9f7 100644 --- a/gcc/cp/ChangeLog +++ b/gcc/cp/ChangeLog @@ -1,5 +1,9 @@ 2015-08-17 Jason Merrill + PR c++/67104 + * constexpr.c (array_index_cmp, find_array_ctor_elt): New. + (cxx_eval_array_reference, cxx_eval_store_expression): Use them. + * constexpr.c (cxx_eval_store_expression): Don't set CONSTRUCTOR_NO_IMPLICIT_ZERO if we have an enclosing CONSTRUCTOR without it. diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c index 35875a84361..1eacb8be9a4 100644 --- a/gcc/cp/constexpr.c +++ b/gcc/cp/constexpr.c @@ -1654,6 +1654,90 @@ cxx_eval_conditional_expression (const constexpr_ctx *ctx, tree t, jump_target); } +/* Returns less than, equal to, or greater than zero if KEY is found to be + less than, to match, or to be greater than the constructor_elt's INDEX. */ + +static int +array_index_cmp (tree key, tree index) +{ + gcc_assert (TREE_CODE (key) == INTEGER_CST); + + switch (TREE_CODE (index)) + { + case INTEGER_CST: + return tree_int_cst_compare (key, index); + case RANGE_EXPR: + { + tree lo = TREE_OPERAND (index, 0); + tree hi = TREE_OPERAND (index, 1); + if (tree_int_cst_lt (key, lo)) + return -1; + else if (tree_int_cst_lt (hi, key)) + return 1; + else + return 0; + } + default: + gcc_unreachable (); + } +} + +/* Returns the index of the constructor_elt of ARY which matches DINDEX, or -1 + if none. If INSERT is true, insert a matching element rather than fail. */ + +static HOST_WIDE_INT +find_array_ctor_elt (tree ary, tree dindex, bool insert = false) +{ + if (tree_int_cst_sgn (dindex) < 0) + return -1; + + unsigned HOST_WIDE_INT i = tree_to_uhwi (dindex); + vec *elts = CONSTRUCTOR_ELTS (ary); + unsigned HOST_WIDE_INT len = vec_safe_length (elts); + + unsigned HOST_WIDE_INT end = len; + unsigned HOST_WIDE_INT begin = 0; + + /* If the last element of the CONSTRUCTOR has its own index, we can assume + that the same is true of the other elements and index directly. */ + if (end > 0) + { + tree cindex = (*elts)[end-1].index; + if (TREE_CODE (cindex) == INTEGER_CST + && compare_tree_int (cindex, end-1) == 0) + { + if (i < end) + return i; + else + begin = end; + } + } + + /* Otherwise, find a matching index by means of a binary search. */ + while (begin != end) + { + unsigned HOST_WIDE_INT middle = (begin + end) / 2; + + int cmp = array_index_cmp (dindex, (*elts)[middle].index); + if (cmp < 0) + end = middle; + else if (cmp > 0) + begin = middle + 1; + else + return middle; + } + + if (insert) + { + constructor_elt e = { dindex, NULL_TREE }; + vec_safe_insert (CONSTRUCTOR_ELTS (ary), end, e); + return end; + } + + return -1; +} + + /* Subroutine of cxx_eval_constant_expression. Attempt to reduce a reference to an array slot. */ @@ -1699,36 +1783,26 @@ cxx_eval_array_reference (const constexpr_ctx *ctx, tree t, } i = tree_to_shwi (index); - bool found = true; - if (TREE_CODE (ary) == CONSTRUCTOR && len - && (TREE_CODE (CONSTRUCTOR_ELT (ary, len-1)->index) == RANGE_EXPR - || compare_tree_int (CONSTRUCTOR_ELT (ary, len-1)->index, len-1))) + if (i < 0) { - /* The last element doesn't match its position in the array; this must be - a sparse array from cxx_eval_store_expression. So iterate. */ - found = false; - vec *v = CONSTRUCTOR_ELTS (ary); - constructor_elt *e; - for (unsigned ix = 0; vec_safe_iterate (v, ix, &e); ++ix) - { - if (TREE_CODE (e->index) == RANGE_EXPR) - { - tree lo = TREE_OPERAND (e->index, 0); - tree hi = TREE_OPERAND (e->index, 1); - if (tree_int_cst_le (lo, index) && tree_int_cst_le (index, hi)) - found = true; - } - else if (tree_int_cst_equal (e->index, index)) - found = true; - if (found) - { - i = ix; - break; - } - } + if (!ctx->quiet) + error ("negative array subscript"); + *non_constant_p = true; + return t; + } + + bool found; + if (TREE_CODE (ary) == CONSTRUCTOR) + { + HOST_WIDE_INT ix = find_array_ctor_elt (ary, index); + found = (ix >= 0); + if (found) + i = ix; } + else + found = (i < len); - if (i >= len || !found) + if (!found) { if (tree_int_cst_lt (index, array_type_nelts_top (TREE_TYPE (ary)))) { @@ -1757,13 +1831,6 @@ cxx_eval_array_reference (const constexpr_ctx *ctx, tree t, *non_constant_p = true; return t; } - else if (i < 0) - { - if (!ctx->quiet) - error ("negative array subscript"); - *non_constant_p = true; - return t; - } if (TREE_CODE (ary) == CONSTRUCTOR) return (*CONSTRUCTOR_ELTS (ary))[i].value; @@ -2698,21 +2765,33 @@ cxx_eval_store_expression (const constexpr_ctx *ctx, tree t, subobjects will also be zero-initialized. */ no_zero_init = CONSTRUCTOR_NO_IMPLICIT_ZERO (*valp); - constructor_elt ce; + enum tree_code code = TREE_CODE (type); type = refs->pop(); - ce.index = refs->pop(); - ce.value = NULL_TREE; + tree index = refs->pop(); - unsigned HOST_WIDE_INT idx = 0; constructor_elt *cep = NULL; - for (idx = 0; - vec_safe_iterate (CONSTRUCTOR_ELTS (*valp), idx, &cep); - idx++) - /* ??? slow */ - if (cp_tree_equal (ce.index, cep->index)) - break; - if (!cep) - cep = vec_safe_push (CONSTRUCTOR_ELTS (*valp), ce); + if (code == ARRAY_TYPE) + { + HOST_WIDE_INT i + = find_array_ctor_elt (*valp, index, /*insert*/true); + gcc_assert (i >= 0); + cep = CONSTRUCTOR_ELT (*valp, i); + gcc_assert (TREE_CODE (cep->index) != RANGE_EXPR); + } + else + { + gcc_assert (TREE_CODE (index) == FIELD_DECL); + for (unsigned HOST_WIDE_INT idx = 0; + vec_safe_iterate (CONSTRUCTOR_ELTS (*valp), idx, &cep); + idx++) + if (index == cep->index) + break; + if (!cep) + { + constructor_elt ce = { index, NULL_TREE }; + cep = vec_safe_push (CONSTRUCTOR_ELTS (*valp), ce); + } + } valp = &cep->value; } release_tree_vector (refs); -- 2.30.2