diff options
| -rw-r--r-- | gcc/ChangeLog | 44 | ||||
| -rw-r--r-- | gcc/Makefile.in | 1 | ||||
| -rw-r--r-- | gcc/doc/generic.texi | 75 | ||||
| -rw-r--r-- | gcc/fold-const.c | 5 | ||||
| -rw-r--r-- | gcc/lto-streamer-out.c | 12 | ||||
| -rw-r--r-- | gcc/lto/ChangeLog | 4 | ||||
| -rw-r--r-- | gcc/lto/lto.c | 13 | ||||
| -rw-r--r-- | gcc/tree-core.h | 15 | ||||
| -rw-r--r-- | gcc/tree-streamer-in.c | 12 | ||||
| -rw-r--r-- | gcc/tree-streamer-out.c | 13 | ||||
| -rw-r--r-- | gcc/tree-vector-builder.c | 64 | ||||
| -rw-r--r-- | gcc/tree-vector-builder.h | 135 | ||||
| -rw-r--r-- | gcc/tree.c | 261 | ||||
| -rw-r--r-- | gcc/tree.def | 2 | ||||
| -rw-r--r-- | gcc/tree.h | 35 | ||||
| -rw-r--r-- | gcc/vector-builder.h | 394 |
16 files changed, 1015 insertions, 70 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 21aa49b05bf..aa3bc51c342 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,47 @@ +2017-12-07 Richard Sandiford <richard.sandiford@arm.com> + + * doc/generic.texi (VECTOR_CST): Describe new representation of + vector constants. + * vector-builder.h: New file. + * tree-vector-builder.h: Likewise. + * tree-vector-builder.c: Likewise. + * Makefile.in (OBJS): Add tree-vector-builder.o. + * tree.def (VECTOR_CST): Update comment to refer to generic.texi. + * tree-core.h (tree_base): Add a vector_cst field to the u union. + (tree_vector): Change the number of elements to + vector_cst_encoded_nelts. + * tree.h (VECTOR_CST_NELTS): Redefine using TYPE_VECTOR_SUBPARTS. + (VECTOR_CST_ELTS): Delete. + (VECTOR_CST_ELT): Redefine using vector_cst_elt. + (VECTOR_CST_LOG2_NPATTERNS, VECTOR_CST_NPATTERNS): New macros. + (VECTOR_CST_NELTS_PER_PATTERN, VECTOR_CST_DUPLICATE_P): Likewise. + (VECTOR_CST_STEPPED_P, VECTOR_CST_ENCODED_ELTS): Likewise. + (VECTOR_CST_ENCODED_ELT): Likewise. + (vector_cst_encoded_nelts): New function. + (make_vector): Take the values of VECTOR_CST_LOG2_NPATTERNS and + VECTOR_CST_NELTS_PER_PATTERN as arguments. + (vector_cst_int_elt, vector_cst_elt): Declare. + * tree.c: Include tree-vector-builder.h. + (tree_code_size): Abort if passed VECTOR_CST. + (tree_size): Update for new VECTOR_CST layout. + (make_vector): Take the values of VECTOR_CST_LOG2_NPATTERNS and + VECTOR_CST_NELTS_PER_PATTERN as arguments. + (build_vector): Use tree_vector_builder. + (vector_cst_int_elt, vector_cst_elt): New functions. + (drop_tree_overflow): For VECTOR_CST, drop the TREE_OVERFLOW from the + encoded elements and then create the vector in the canonical form. + (check_vector_cst, check_vector_cst_duplicate, check_vector_cst_fill) + (check_vector_cst_stepped, test_vector_cst_patterns): New functions. + (tree_c_tests): Call test_vector_cst_patterns. + * lto-streamer-out.c (DFS::DFS_write_tree_body): Handle the new + VECTOR_CST fields. + (hash_tree): Likewise. + * tree-streamer-out.c (write_ts_vector_tree_pointers): Likewise. + (streamer_write_tree_header): Likewise. + * tree-streamer-in.c (lto_input_ts_vector_tree_pointers): Likewise. + (streamer_alloc_tree): Likewise. Update call to make_vector. + * fold-const.c (fold_ternary_loc): Avoid using VECTOR_CST_ELTS. + 2017-12-07 Richard Sandiford <richard.sandiford@linaro.org> * selftest.h (ASSERT_TRUE_AT, ASSERT_FALSE_AT, ASSERT_EQ_AT) diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 216fb0d8d45..f6e59cde8df 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1574,6 +1574,7 @@ OBJS = \ tree-vect-loop-manip.o \ tree-vect-slp.o \ tree-vectorizer.o \ + tree-vector-builder.o \ tree-vrp.o \ tree.o \ typed-splay-tree.o \ diff --git a/gcc/doc/generic.texi b/gcc/doc/generic.texi index 17f38df3d4c..75c448e7330 100644 --- a/gcc/doc/generic.texi +++ b/gcc/doc/generic.texi @@ -1084,10 +1084,77 @@ These nodes are used to represent complex number constants, that is a imaginary parts respectively. @item VECTOR_CST -These nodes are used to represent vector constants, whose parts are -constant nodes. Each individual constant node is either an integer or a -double constant node. The first operand is a @code{TREE_LIST} of the -constant nodes and is accessed through @code{TREE_VECTOR_CST_ELTS}. +These nodes are used to represent vector constants. Each vector +constant @var{v} is treated as a specific instance of an arbitrary-length +sequence that itself contains @samp{VECTOR_CST_NPATTERNS (@var{v})} +interleaved patterns. Each pattern has the form: + +@smallexample +@{ @var{base0}, @var{base1}, @var{base1} + @var{step}, @var{base1} + @var{step} * 2, @dots{} @} +@end smallexample + +The first three elements in each pattern are enough to determine the +values of the other elements. However, if all @var{step}s are zero, +only the first two elements are needed. If in addition each @var{base1} +is equal to the corresponding @var{base0}, only the first element in +each pattern is needed. The number of encoded elements per pattern +is given by @samp{VECTOR_CST_NELTS_PER_PATTERN (@var{v})}. + +For example, the constant: + +@smallexample +@{ 0, 1, 2, 6, 3, 8, 4, 10, 5, 12, 6, 14, 7, 16, 8, 18 @} +@end smallexample + +is interpreted as an interleaving of the sequences: + +@smallexample +@{ 0, 2, 3, 4, 5, 6, 7, 8 @} +@{ 1, 6, 8, 10, 12, 14, 16, 18 @} +@end smallexample + +where the sequences are represented by the following patterns: + +@smallexample +@var{base0} == 0, @var{base1} == 2, @var{step} == 1 +@var{base0} == 1, @var{base1} == 6, @var{step} == 2 +@end smallexample + +In this case: + +@smallexample +VECTOR_CST_NPATTERNS (@var{v}) == 2 +VECTOR_CST_NELTS_PER_PATTERN (@var{v}) == 3 +@end smallexample + +The vector is therefore encoded using the first 6 elements +(@samp{@{ 0, 1, 2, 6, 3, 8 @}}), with the remaining 10 elements +being implicit extensions of them. + +Sometimes this scheme can create two possible encodings of the same +vector. For example @{ 0, 1 @} could be seen as two patterns with +one element each or one pattern with two elements (@var{base0} and +@var{base1}). The canonical encoding is always the one with the +fewest patterns or (if both encodings have the same number of +petterns) the one with the fewest encoded elements. + +@samp{vector_cst_encoding_nelts (@var{v})} gives the total number of +encoded elements in @var{v}, which is 6 in the example above. +@code{VECTOR_CST_ENCODED_ELTS (@var{v})} gives a pointer to the elements +encoded in @var{v} and @code{VECTOR_CST_ENCODED_ELT (@var{v}, @var{i})} +accesses the value of encoded element @var{i}. + +@samp{VECTOR_CST_DUPLICATE_P (@var{v})} is true if @var{v} simply contains +repeated instances of @samp{VECTOR_CST_NPATTERNS (@var{v})} values. This is +a shorthand for testing @samp{VECTOR_CST_NELTS_PER_PATTERN (@var{v}) == 1}. + +@samp{VECTOR_CST_STEPPED_P (@var{v})} is true if at least one +pattern in @var{v} has a nonzero step. This is a shorthand for +testing @samp{VECTOR_CST_NELTS_PER_PATTERN (@var{v}) == 3}. + +The utility function @code{vector_cst_elt} gives the value of an +arbitrary index as a @code{tree}. @code{vector_cst_int_elt} gives +the same value as a @code{wide_int}. @item STRING_CST These nodes represent string-constants. The @code{TREE_STRING_LENGTH} diff --git a/gcc/fold-const.c b/gcc/fold-const.c index 8c8e52a2a27..2df78637f42 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -11610,9 +11610,8 @@ fold_ternary_loc (location_t loc, enum tree_code code, tree type, unsigned int nelts = VECTOR_CST_NELTS (arg0); auto_vec<tree, 32> elts (nelts); elts.quick_grow (nelts); - memcpy (&elts[0], VECTOR_CST_ELTS (arg0), - sizeof (tree) * nelts); - elts[k] = arg1; + for (unsigned int i = 0; i < VECTOR_CST_NELTS (arg0); ++i) + elts[i] = (i == k ? arg1 : VECTOR_CST_ELT (arg0, i)); return build_vector (type, elts); } } diff --git a/gcc/lto-streamer-out.c b/gcc/lto-streamer-out.c index 0442ec72d06..4efa9c9c2fc 100644 --- a/gcc/lto-streamer-out.c +++ b/gcc/lto-streamer-out.c @@ -747,8 +747,9 @@ DFS::DFS_write_tree_body (struct output_block *ob, if (CODE_CONTAINS_STRUCT (code, TS_VECTOR)) { - for (unsigned i = 0; i < VECTOR_CST_NELTS (expr); ++i) - DFS_follow_tree_edge (VECTOR_CST_ELT (expr, i)); + unsigned int count = vector_cst_encoded_nelts (expr); + for (unsigned int i = 0; i < count; ++i) + DFS_follow_tree_edge (VECTOR_CST_ENCODED_ELT (expr, i)); } if (CODE_CONTAINS_STRUCT (code, TS_COMPLEX)) @@ -1195,8 +1196,11 @@ hash_tree (struct streamer_tree_cache_d *cache, hash_map<tree, hashval_t> *map, } if (CODE_CONTAINS_STRUCT (code, TS_VECTOR)) - for (unsigned i = 0; i < VECTOR_CST_NELTS (t); ++i) - visit (VECTOR_CST_ELT (t, i)); + { + unsigned int count = vector_cst_encoded_nelts (t); + for (unsigned int i = 0; i < count; ++i) + visit (VECTOR_CST_ENCODED_ELT (t, i)); + } if (CODE_CONTAINS_STRUCT (code, TS_COMPLEX)) { diff --git a/gcc/lto/ChangeLog b/gcc/lto/ChangeLog index b8260a0690d..4823dc25f3e 100644 --- a/gcc/lto/ChangeLog +++ b/gcc/lto/ChangeLog @@ -1,3 +1,7 @@ +2017-12-07 Richard Sandiford <richard.sandiford@arm.com> + + * lto.c (compare_tree_sccs_1): Compare the new VECTOR_CST flags. + 2017-12-07 Martin Sebor <msebor@redhat.com> PR c/81544 diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c index ae9bae84016..e330644e2ef 100644 --- a/gcc/lto/lto.c +++ b/gcc/lto/lto.c @@ -1065,6 +1065,12 @@ compare_tree_sccs_1 (tree t1, tree t2, tree **map) TREE_FIXED_CST_PTR (t1), TREE_FIXED_CST_PTR (t2))) return false; + if (CODE_CONTAINS_STRUCT (code, TS_VECTOR)) + { + compare_values (VECTOR_CST_LOG2_NPATTERNS); + compare_values (VECTOR_CST_NELTS_PER_PATTERN); + } + if (CODE_CONTAINS_STRUCT (code, TS_DECL_COMMON)) { compare_values (DECL_MODE); @@ -1281,11 +1287,12 @@ compare_tree_sccs_1 (tree t1, tree t2, tree **map) if (CODE_CONTAINS_STRUCT (code, TS_VECTOR)) { - unsigned i; /* Note that the number of elements for EXPR has already been emitted in EXPR's header (see streamer_write_tree_header). */ - for (i = 0; i < VECTOR_CST_NELTS (t1); ++i) - compare_tree_edges (VECTOR_CST_ELT (t1, i), VECTOR_CST_ELT (t2, i)); + unsigned int count = vector_cst_encoded_nelts (t1); + for (unsigned int i = 0; i < count; ++i) + compare_tree_edges (VECTOR_CST_ENCODED_ELT (t1, i), + VECTOR_CST_ENCODED_ELT (t2, i)); } if (CODE_CONTAINS_STRUCT (code, TS_COMPLEX)) diff --git a/gcc/tree-core.h b/gcc/tree-core.h index 7672541f1b4..f225f999fc8 100644 --- a/gcc/tree-core.h +++ b/gcc/tree-core.h @@ -972,8 +972,17 @@ struct GTY(()) tree_base { /* VEC length. This field is only used with TREE_VEC. */ int length; - /* Number of elements. This field is only used with VECTOR_CST. */ - unsigned int nelts; + /* This field is only used with VECTOR_CST. */ + struct { + /* The value of VECTOR_CST_LOG2_NPATTERNS. */ + unsigned int log2_npatterns : 8; + + /* The value of VECTOR_CST_NELTS_PER_PATTERN. */ + unsigned int nelts_per_pattern : 8; + + /* For future expansion. */ + unsigned int unused : 16; + } vector_cst; /* SSA version number. This field is only used with SSA_NAME. */ unsigned int version; @@ -1325,7 +1334,7 @@ struct GTY(()) tree_complex { struct GTY(()) tree_vector { struct tree_typed typed; - tree GTY ((length ("VECTOR_CST_NELTS ((tree) &%h)"))) elts[1]; + tree GTY ((length ("vector_cst_encoded_nelts ((tree) &%h)"))) elts[1]; }; struct GTY(()) tree_identifier { diff --git a/gcc/tree-streamer-in.c b/gcc/tree-streamer-in.c index 36402c6a39c..09201393cd3 100644 --- a/gcc/tree-streamer-in.c +++ b/gcc/tree-streamer-in.c @@ -592,8 +592,10 @@ streamer_alloc_tree (struct lto_input_block *ib, struct data_in *data_in, } else if (CODE_CONTAINS_STRUCT (code, TS_VECTOR)) { - HOST_WIDE_INT len = streamer_read_hwi (ib); - result = make_vector (len); + bitpack_d bp = streamer_read_bitpack (ib); + unsigned int log2_npatterns = bp_unpack_value (&bp, 8); + unsigned int nelts_per_pattern = bp_unpack_value (&bp, 8); + result = make_vector (log2_npatterns, nelts_per_pattern); } else if (CODE_CONTAINS_STRUCT (code, TS_BINFO)) { @@ -650,9 +652,9 @@ static void lto_input_ts_vector_tree_pointers (struct lto_input_block *ib, struct data_in *data_in, tree expr) { - unsigned i; - for (i = 0; i < VECTOR_CST_NELTS (expr); ++i) - VECTOR_CST_ELT (expr, i) = stream_read_tree (ib, data_in); + unsigned int count = vector_cst_encoded_nelts (expr); + for (unsigned int i = 0; i < count; ++i) + VECTOR_CST_ENCODED_ELT (expr, i) = stream_read_tree (ib, data_in); } diff --git a/gcc/tree-streamer-out.c b/gcc/tree-streamer-out.c index 08c58a4709d..921cb874dcc 100644 --- a/gcc/tree-streamer-out.c +++ b/gcc/tree-streamer-out.c @@ -533,11 +533,11 @@ write_ts_common_tree_pointers (struct output_block *ob, tree expr, bool ref_p) static void write_ts_vector_tree_pointers (struct output_block *ob, tree expr, bool ref_p) { - unsigned i; /* Note that the number of elements for EXPR has already been emitted in EXPR's header (see streamer_write_tree_header). */ - for (i = 0; i < VECTOR_CST_NELTS (expr); ++i) - stream_write_tree (ob, VECTOR_CST_ELT (expr, i), ref_p); + unsigned int count = vector_cst_encoded_nelts (expr); + for (unsigned int i = 0; i < count; ++i) + stream_write_tree (ob, VECTOR_CST_ENCODED_ELT (expr, i), ref_p); } @@ -960,7 +960,12 @@ streamer_write_tree_header (struct output_block *ob, tree expr) else if (CODE_CONTAINS_STRUCT (code, TS_IDENTIFIER)) write_identifier (ob, ob->main_stream, expr); else if (CODE_CONTAINS_STRUCT (code, TS_VECTOR)) - streamer_write_hwi (ob, VECTOR_CST_NELTS (expr)); + { + bitpack_d bp = bitpack_create (ob->main_stream); + bp_pack_value (&bp, VECTOR_CST_LOG2_NPATTERNS (expr), 8); + bp_pack_value (&bp, VECTOR_CST_NELTS_PER_PATTERN (expr), 8); + streamer_write_bitpack (&bp); + } else if (CODE_CONTAINS_STRUCT (code, TS_VEC)) streamer_write_hwi (ob, TREE_VEC_LENGTH (expr)); else if (CODE_CONTAINS_STRUCT (code, TS_BINFO)) diff --git a/gcc/tree-vector-builder.c b/gcc/tree-vector-builder.c new file mode 100644 index 00000000000..708bf0e1a05 --- /dev/null +++ b/gcc/tree-vector-builder.c @@ -0,0 +1,64 @@ +/* A class for building vector tree constants. + Copyright (C) 2017 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "fold-const.h" +#include "tree-vector-builder.h" + +/* Try to start building a new vector of type TYPE that holds the result of + a unary operation on VECTOR_CST T. ALLOW_STEPPED_P is true if the + operation can handle stepped encodings directly, without having to + expand the full sequence. + + Return true if the operation is possible, which it always is when + ALLOW_STEPPED_P is true. Leave the builder unchanged otherwise. */ + +bool +tree_vector_builder::new_unary_operation (tree type, tree t, + bool allow_stepped_p) +{ + unsigned int full_nelts = TYPE_VECTOR_SUBPARTS (type); + gcc_assert (full_nelts == TYPE_VECTOR_SUBPARTS (TREE_TYPE (t))); + unsigned int npatterns = VECTOR_CST_NPATTERNS (t); + unsigned int nelts_per_pattern = VECTOR_CST_NELTS_PER_PATTERN (t); + if (!allow_stepped_p && nelts_per_pattern > 2) + { + npatterns = full_nelts; + nelts_per_pattern = 1; + } + new_vector (type, npatterns, nelts_per_pattern); + return true; +} + +/* Return a VECTOR_CST for the current constant. */ + +tree +tree_vector_builder::build () +{ + finalize (); + gcc_assert (pow2p_hwi (npatterns ())); + tree v = make_vector (exact_log2 (npatterns ()), nelts_per_pattern ()); + TREE_TYPE (v) = m_type; + memcpy (VECTOR_CST_ENCODED_ELTS (v), address (), + encoded_nelts () * sizeof (tree)); + return v; +} diff --git a/gcc/tree-vector-builder.h b/gcc/tree-vector-builder.h new file mode 100644 index 00000000000..b7b56259b8c --- /dev/null +++ b/gcc/tree-vector-builder.h @@ -0,0 +1,135 @@ +/* A class for building vector tree constants. + Copyright (C) 2017 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_TREE_VECTOR_BUILDER_H +#define GCC_TREE_VECTOR_BUILDER_H + +#include "vector-builder.h" + +/* This class is used to build VECTOR_CSTs from a sequence of elements. + See vector_builder for more details. */ +class tree_vector_builder : public vector_builder<tree, tree_vector_builder> +{ + typedef vector_builder<tree, tree_vector_builder> parent; + friend class vector_builder<tree, tree_vector_builder>; + +public: + tree_vector_builder () : m_type (0) {} + tree_vector_builder (tree, unsigned int, unsigned int); + tree build (); + + tree type () const { return m_type; } + + void new_vector (tree, unsigned int, unsigned int); + bool new_unary_operation (tree, tree, bool); + +private: + bool equal_p (const_tree, const_tree) const; + bool allow_steps_p () const; + bool integral_p (const_tree) const; + wide_int step (const_tree, const_tree) const; + bool can_elide_p (const_tree) const; + void note_representative (tree *, tree); + + tree m_type; +}; + +/* Create a new builder for a vector of type TYPE. Initially encode the + value as NPATTERNS interleaved patterns with NELTS_PER_PATTERN elements + each. */ + +inline +tree_vector_builder::tree_vector_builder (tree type, unsigned int npatterns, + unsigned int nelts_per_pattern) +{ + new_vector (type, npatterns, nelts_per_pattern); +} + +/* Start building a new vector of type TYPE. Initially encode the value + as NPATTERNS interleaved patterns with NELTS_PER_PATTERN elements each. */ + +inline void +tree_vector_builder::new_vector (tree type, unsigned int npatterns, + unsigned int nelts_per_pattern) +{ + m_type = type; + parent::new_vector (TYPE_VECTOR_SUBPARTS (type), npatterns, + nelts_per_pattern); +} + +/* Return true if elements I1 and I2 are equal. */ + +inline bool +tree_vector_builder::equal_p (const_tree elt1, const_tree elt2) const +{ + return operand_equal_p (elt1, elt2, 0); +} + +/* Return true if a stepped representation is OK. We don't allow + linear series for anything other than integers, to avoid problems + with rounding. */ + +inline bool +tree_vector_builder::allow_steps_p () const +{ + return INTEGRAL_TYPE_P (TREE_TYPE (m_type)); +} + +/* Return true if ELT can be interpreted as an integer. */ + +inline bool +tree_vector_builder::integral_p (const_tree elt) const +{ + return TREE_CODE (elt) == INTEGER_CST; +} + +/* Return the value of element ELT2 minus the value of element ELT1. + Both elements are known to be INTEGER_CSTs. */ + +inline wide_int +tree_vector_builder::step (const_tree elt1, const_tree elt2) const +{ + return wi::to_wide (elt2) - wi::to_wide (elt1); +} + +/* Return true if we can drop element ELT, even if the retained elements + are different. Return false if this would mean losing overflow + information. */ + +inline bool +tree_vector_builder::can_elide_p (const_tree elt) const +{ + return !CONSTANT_CLASS_P (elt) || !TREE_OVERFLOW (elt); +} + +/* Record that ELT2 is being elided, given that ELT1_PTR points to the last + encoded element for the containing pattern. */ + +inline void +tree_vector_builder::note_representative (tree *elt1_ptr, tree elt2) +{ + if (CONSTANT_CLASS_P (elt2) && TREE_OVERFLOW (elt2)) + { + gcc_assert (operand_equal_p (*elt1_ptr, elt2, 0)); + if (!TREE_OVERFLOW (elt2)) + *elt1_ptr = elt2; + } +} + +#endif diff --git a/gcc/tree.c b/gcc/tree.c index 5416866a644..e3a60fb3e14 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -66,6 +66,7 @@ along with GCC; see the file COPYING3. If not see #include "attribs.h" #include "rtl.h" #include "regs.h" +#include "tree-vector-builder.h" /* Tree code classes. */ @@ -837,7 +838,7 @@ tree_code_size (enum tree_code code) case REAL_CST: return sizeof (tree_real_cst); case FIXED_CST: return sizeof (tree_fixed_cst); case COMPLEX_CST: return sizeof (tree_complex); - case VECTOR_CST: return sizeof (tree_vector); + case VECTOR_CST: gcc_unreachable (); case STRING_CST: gcc_unreachable (); default: gcc_checking_assert (code >= NUM_TREE_CODES); @@ -897,7 +898,7 @@ tree_size (const_tree node) case VECTOR_CST: return (sizeof (struct tree_vector) - + (VECTOR_CST_NELTS (node) - 1) * sizeof (tree)); + + (vector_cst_encoded_nelts (node) - 1) * sizeof (tree)); case STRING_CST: return TREE_STRING_LENGTH (node) + offsetof (struct tree_string, str) + 1; @@ -1708,13 +1709,19 @@ cst_and_fits_in_hwi (const_tree x) && (tree_fits_shwi_p (x) || tree_fits_uhwi_p (x))); } -/* Build a newly constructed VECTOR_CST node of length LEN. */ +/* Build a newly constructed VECTOR_CST with the given values of + (VECTOR_CST_)LOG2_NPATTERNS and (VECTOR_CST_)NELTS_PER_PATTERN. */ tree -make_vector (unsigned len MEM_STAT_DECL) +make_vector (unsigned log2_npatterns, + unsigned int nelts_per_pattern MEM_STAT_DECL) { + gcc_assert (IN_RANGE (nelts_per_pattern, 1, 3)); tree t; - unsigned length = (len - 1) * sizeof (tree) + sizeof (struct tree_vector); + unsigned npatterns = 1 << log2_npatterns; + unsigned encoded_nelts = npatterns * nelts_per_pattern; + unsigned length = (sizeof (struct tree_vector) + + (encoded_nelts - 1) * sizeof (tree)); record_node_allocation_statistics (VECTOR_CST, length); @@ -1722,7 +1729,8 @@ make_vector (unsigned len MEM_STAT_DECL) TREE_SET_CODE (t, VECTOR_CST); TREE_CONSTANT (t) = 1; - VECTOR_CST_NELTS (t) = len; + VECTOR_CST_LOG2_NPATTERNS (t) = log2_npatterns; + VECTOR_CST_NELTS_PER_PATTERN (t) = nelts_per_pattern; return t; } @@ -1733,29 +1741,10 @@ make_vector (unsigned len MEM_STAT_DECL) tree build_vector (tree type, vec<tree> vals MEM_STAT_DECL) { - unsigned int nelts = vals.length (); - gcc_assert (nelts == TYPE_VECTOR_SUBPARTS (type)); - int over = 0; - unsigned cnt = 0; - tree v = make_vector (nelts); - TREE_TYPE (v) = type; - - /* Iterate through elements and check for overflow. */ - for (cnt = 0; cnt < nelts; ++cnt) - { - tree value = vals[cnt]; - - VECTOR_CST_ELT (v, cnt) = value; - - /* Don't crash if we get an address constant. */ - if (!CONSTANT_CLASS_P (value)) - continue; - - over |= TREE_OVERFLOW (value); - } - - TREE_OVERFLOW (v) = over; - return v; + gcc_assert (vals.length () == TYPE_VECTOR_SUBPARTS (type)); + tree_vector_builder builder (type, vals.length (), 1); + builder.splice (vals); + return builder.build (); } /* Return a new VECTOR_CST node whose type is TYPE and whose values @@ -10370,6 +10359,59 @@ build_opaque_vector_type (tree innertype, int nunits) return cand; } +/* Return the value of element I of VECTOR_CST T as a wide_int. */ + +wide_int +vector_cst_int_elt (const_tree t, unsigned int i) +{ + /* First handle elements that are directly encoded. */ + unsigned int encoded_nelts = vector_cst_encoded_nelts (t); + if (i < encoded_nelts) + return wi::to_wide (VECTOR_CST_ENCODED_ELT (t, i)); + + /* Identify the pattern that contains element I and work out the index of + the last encoded element for that pattern. */ + unsigned int npatterns = VECTOR_CST_NPATTERNS (t); + unsigned int pattern = i % npatterns; + unsigned int count = i / npatterns; + unsigned int final_i = encoded_nelts - npatterns + pattern; + + /* If there are no steps, the final encoded value is the right one. */ + if (!VECTOR_CST_STEPPED_P (t)) + return wi::to_wide (VECTOR_CST_ENCODED_ELT (t, final_i)); + + /* Otherwise work out the value from the last two encoded elements. */ + tree v1 = VECTOR_CST_ENCODED_ELT (t, final_i - npatterns); + tree v2 = VECTOR_CST_ENCODED_ELT (t, final_i); + wide_int diff = wi::to_wide (v2) - wi::to_wide (v1); + return wi::to_wide (v2) + (count - 2) * diff; +} + +/* Return the value of element I of VECTOR_CST T. */ + +tree +vector_cst_elt (const_tree t, unsigned int i) +{ + /* First handle elements that are directly encoded. */ + unsigned int encoded_nelts = vector_cst_encoded_nelts (t); + if (i < encoded_nelts) + return VECTOR_CST_ENCODED_ELT (t, i); + + /* If there are no steps, the final encoded value is the right one. */ + if (!VECTOR_CST_STEPPED_P (t)) + { + /* Identify the pattern that contains element I and work out the index of + the last encoded element for that pattern. */ + unsigned int npatterns = VECTOR_CST_NPATTERNS (t); + unsigned int pattern = i % npatterns; + unsigned int final_i = encoded_nelts - npatterns + pattern; + return VECTOR_CST_ENCODED_ELT (t, final_i); + } + + /* Otherwise work out the value from the last two encoded elements. */ + return wide_int_to_tree (TREE_TYPE (TREE_TYPE (t)), + vector_cst_int_elt (t, i)); +} /* Given an initializer INIT, return TRUE if INIT is zero or some aggregate of zeros. Otherwise return FALSE. */ @@ -12451,6 +12493,23 @@ drop_tree_overflow (tree t) if (TREE_CODE (t) == INTEGER_CST) return wide_int_to_tree (TREE_TYPE (t), wi::to_wide (t)); + /* For VECTOR_CST, remove the overflow bits from the encoded elements + and canonicalize the result. */ + if (TREE_CODE (t) == VECTOR_CST) + { + tree_vector_builder builder; + builder.new_unary_operation (TREE_TYPE (t), t, true); + unsigned int count = builder.encoded_nelts (); + for (unsigned int i = 0; i < count; ++i) + { + tree elt = VECTOR_CST_ELT (t, i); + if (TREE_OVERFLOW (elt)) + elt = drop_tree_overflow (elt); + builder.quick_push (elt); + } + return builder.build (); + } + /* Otherwise, as all tcc_constants are possibly shared, copy the node and drop the flag. */ t = copy_node (t); @@ -12465,15 +12524,7 @@ drop_tree_overflow (tree t) if (TREE_OVERFLOW (TREE_IMAGPART (t))) TREE_IMAGPART (t) = drop_tree_overflow (TREE_IMAGPART (t)); } - if (TREE_CODE (t) == VECTOR_CST) - { - for (unsigned i = 0; i < VECTOR_CST_NELTS (t); ++i) - { - tree& elt = VECTOR_CST_ELT (t, i); - if (TREE_OVERFLOW (elt)) - elt = drop_tree_overflow (elt); - } - } + return t; } @@ -14016,6 +14067,139 @@ test_labels () ASSERT_FALSE (FORCED_LABEL (label_decl)); } +/* Check that VECTOR_CST ACTUAL contains the elements in EXPECTED. */ + +static void +check_vector_cst (vec<tree> expected, tree actual) +{ + ASSERT_EQ (expected.length (), TYPE_VECTOR_SUBPARTS (TREE_TYPE (actual))); + for (unsigned int i = 0; i < expected.length (); ++i) + ASSERT_EQ (wi::to_wide (expected[i]), + wi::to_wide (vector_cst_elt (actual, i))); +} + +/* Check that VECTOR_CST ACTUAL contains NPATTERNS duplicated elements, + and that its elements match EXPECTED. */ + +static void +check_vector_cst_duplicate (vec<tree> expected, tree actual, + unsigned int npatterns) +{ + ASSERT_EQ (npatterns, VECTOR_CST_NPATTERNS (actual)); + ASSERT_EQ (1, VECTOR_CST_NELTS_PER_PATTERN (actual)); + ASSERT_EQ (npatterns, vector_cst_encoded_nelts (actual)); + ASSERT_TRUE (VECTOR_CST_DUPLICATE_P (actual)); + ASSERT_FALSE (VECTOR_CST_STEPPED_P (actual)); + check_vector_cst (expected, actual); +} + +/* Check that VECTOR_CST ACTUAL contains NPATTERNS foreground elements + and NPATTERNS background elements, and that its elements match + EXPECTED. */ + +static void +check_vector_cst_fill (vec<tree> expected, tree actual, + unsigned int npatterns) +{ + ASSERT_EQ (npatterns, VECTOR_CST_NPATTERNS (actual)); + ASSERT_EQ (2, VECTOR_CST_NELTS_PER_PATTERN (actual)); + ASSERT_EQ (2 * npatterns, vector_cst_encoded_nelts (actual)); + ASSERT_FALSE (VECTOR_CST_DUPLICATE_P (actual)); + ASSERT_FALSE (VECTOR_CST_STEPPED_P (actual)); + check_vector_cst (expected, actual); +} + +/* Check that VECTOR_CST ACTUAL contains NPATTERNS stepped patterns, + and that its elements match EXPECTED. */ + +static void +check_vector_cst_stepped (vec<tree> expected, tree actual, + unsigned int npatterns) +{ + ASSERT_EQ (npatterns, VECTOR_CST_NPATTERNS (actual)); + ASSERT_EQ (3, VECTOR_CST_NELTS_PER_PATTERN (actual)); + ASSERT_EQ (3 * npatterns, vector_cst_encoded_nelts (actual)); + ASSERT_FALSE (VECTOR_CST_DUPLICATE_P (actual)); + ASSERT_TRUE (VECTOR_CST_STEPPED_P (actual)); + check_vector_cst (expected, actual); +} + +/* Test the creation of VECTOR_CSTs. */ + +static void +test_vector_cst_patterns () +{ + auto_vec<tree, 8> elements (8); + elements.quick_grow (8); + tree element_type = build_nonstandard_integer_type (16, true); + tree vector_type = build_vector_type (element_type, 8); + + /* Test a simple linear series with a base of 0 and a step of 1: + { 0, 1, 2, 3, 4, 5, 6, 7 }. */ + for (unsigned int i = 0; i < 8; ++i) + elements[i] = build_int_cst (element_type, i); + check_vector_cst_stepped (elements, build_vector (vector_type, elements), 1); + + /* Try the same with the first element replaced by 100: + { 100, 1, 2, 3, 4, 5, 6, 7 }. */ + elements[0] = build_int_cst (element_type, 100); + check_vector_cst_stepped (elements, build_vector (vector_type, elements), 1); + + /* Try a series that wraps around. + { 100, 65531, 65532, 65533, 65534, 65535, 0, 1 }. */ + for (unsigned int i = 1; i < 8; ++i) + elements[i] = build_int_cst (element_type, (65530 + i) & 0xffff); + check_vector_cst_stepped (elements, build_vector (vector_type, elements), 1); + + /* Try a downward series: + { 100, 79, 78, 77, 76, 75, 75, 73 }. */ + for (unsigned int i = 1; i < 8; ++i) + elements[i] = build_int_cst (element_type, 80 - i); + check_vector_cst_stepped (elements, build_vector (vector_type, elements), 1); + + /* Try two interleaved series with different bases and steps: + { 100, 53, 66, 206, 62, 212, 58, 218 }. */ + elements[1] = build_int_cst (element_type, 53); + for (unsigned int i = 2; i < 8; i += 2) + { + elements[i] = build_int_cst (element_type, 70 - i * 2); + elements[i + 1] = build_int_cst (element_type, 200 + i * 3); + } + check_vector_cst_stepped (elements, build_vector (vector_type, elements), 2); + + /* Try a duplicated value: + { 100, 100, 100, 100, 100, 100, 100, 100 }. */ + for (unsigned int i = 1; i < 8; ++i) + elements[i] = elements[0]; + check_vector_cst_duplicate (elements, + build_vector (vector_type, elements), 1); + + /* Try an interleaved duplicated value: + { 100, 55, 100, 55, 100, 55, 100, 55 }. */ + elements[1] = build_int_cst (element_type, 55); + for (unsigned int i = 2; i < 8; ++i) + elements[i] = elements[i - 2]; + check_vector_cst_duplicate (elements, + build_vector (vector_type, elements), 2); + + /* Try a duplicated value with 2 exceptions + { 41, 97, 100, 55, 100, 55, 100, 55 }. */ + elements[0] = build_int_cst (element_type, 41); + elements[1] = build_int_cst (element_type, 97); + check_vector_cst_fill (elements, build_vector (vector_type, elements), 2); + + /* Try with and without a step + { 41, 97, 100, 21, 100, 35, 100, 49 }. */ + for (unsigned int i = 3; i < 8; i += 2) + elements[i] = build_int_cst (element_type, i * 7); + check_vector_cst_stepped (elements, build_vector (vector_type, elements), 2); + + /* Try a fully-general constant: + { 41, 97, 100, 21, 100, 9990, 100, 49 }. */ + elements[5] = build_int_cst (element_type, 9990); + check_vector_cst_fill (elements, build_vector (vector_type, elements), 4); +} + /* Run all of the selftests within this file. */ void @@ -14024,6 +14208,7 @@ tree_c_tests () test_integer_constants (); test_identifiers (); test_labels (); + test_vector_cst_patterns (); } } // namespace selftest diff --git a/gcc/tree.def b/gcc/tree.def index 3029dab3e2e..edcb7effd50 100644 --- a/gcc/tree.def +++ b/gcc/tree.def @@ -301,7 +301,7 @@ DEFTREECODE (FIXED_CST, "fixed_cst", tcc_constant, 0) whose contents are other constant nodes. */ DEFTREECODE (COMPLEX_CST, "complex_cst", tcc_constant, 0) -/* Contents are in VECTOR_CST_ELTS field. */ +/* See generic.texi for details. */ DEFTREECODE (VECTOR_CST, "vector_cst", tcc_constant, 0) /* Contents are TREE_STRING_LENGTH and the actual contents of the string. */ diff --git a/gcc/tree.h b/gcc/tree.h index e5a37afcce8..b3cf74779ba 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -1008,10 +1008,24 @@ extern void omp_clause_range_check_failed (const_tree, const char *, int, #define TREE_REALPART(NODE) (COMPLEX_CST_CHECK (NODE)->complex.real) #define TREE_IMAGPART(NODE) (COMPLEX_CST_CHECK (NODE)->complex.imag) -/* In a VECTOR_CST node. */ -#define VECTOR_CST_NELTS(NODE) (VECTOR_CST_CHECK (NODE)->base.u.nelts) -#define VECTOR_CST_ELTS(NODE) (VECTOR_CST_CHECK (NODE)->vector.elts) -#define VECTOR_CST_ELT(NODE,IDX) (VECTOR_CST_CHECK (NODE)->vector.elts[IDX]) +/* In a VECTOR_CST node. See generic.texi for details. */ +#define VECTOR_CST_NELTS(NODE) (TYPE_VECTOR_SUBPARTS (TREE_TYPE (NODE))) +#define VECTOR_CST_ELT(NODE,IDX) vector_cst_elt (NODE, IDX) + +#define VECTOR_CST_LOG2_NPATTERNS(NODE) \ + (VECTOR_CST_CHECK (NODE)->base.u.vector_cst.log2_npatterns) +#define VECTOR_CST_NPATTERNS(NODE) \ + (1U << VECTOR_CST_LOG2_NPATTERNS (NODE)) +#define VECTOR_CST_NELTS_PER_PATTERN(NODE) \ + (VECTOR_CST_CHECK (NODE)->base.u.vector_cst.nelts_per_pattern) +#define VECTOR_CST_DUPLICATE_P(NODE) \ + (VECTOR_CST_NELTS_PER_PATTERN (NODE) == 1) +#define VECTOR_CST_STEPPED_P(NODE) \ + (VECTOR_CST_NELTS_PER_PATTERN (NODE) == 3) +#define VECTOR_CST_ENCODED_ELTS(NODE) \ + (VECTOR_CST_CHECK (NODE)->vector.elts) +#define VECTOR_CST_ENCODED_ELT(NODE, ELT) \ + (VECTOR_CST_CHECK (NODE)->vector.elts[ELT]) /* Define fields and accessors for some special-purpose tree nodes. */ @@ -3882,6 +3896,14 @@ id_equal (const char *str, const_tree id) ((NODE) == error_mark_node \ || ((NODE) && TREE_TYPE ((NODE)) == error_mark_node)) +/* Return the number of elements encoded directly in a VECTOR_CST. */ + +inline unsigned int +vector_cst_encoded_nelts (const_tree t) +{ + return VECTOR_CST_NPATTERNS (t) * VECTOR_CST_NELTS_PER_PATTERN (t); +} + extern tree decl_assembler_name (tree); extern void overwrite_decl_assembler_name (tree decl, tree name); extern tree decl_comdat_group (const_tree); @@ -4021,7 +4043,7 @@ extern tree force_fit_type (tree, const wide_int_ref &, int, bool); extern tree build_int_cst (tree, HOST_WIDE_INT); extern tree build_int_cstu (tree type, unsigned HOST_WIDE_INT cst); extern tree build_int_cst_type (tree, HOST_WIDE_INT); -extern tree make_vector (unsigned CXX_MEM_STAT_INFO); +extern tree make_vector (unsigned, unsigned CXX_MEM_STAT_INFO); extern tree build_vector (tree, vec<tree> CXX_MEM_STAT_INFO); extern tree build_vector_from_ctor (tree, vec<constructor_elt, va_gc> *); extern tree build_vector_from_val (tree, tree); @@ -4268,6 +4290,9 @@ extern tree first_field (const_tree); extern bool initializer_zerop (const_tree); +extern wide_int vector_cst_int_elt (const_tree, unsigned int); +extern tree vector_cst_elt (const_tree, unsigned int); + /* Given a vector VEC, return its first element if all elements are the same. Otherwise return NULL_TREE. */ diff --git a/gcc/vector-builder.h b/gcc/vector-builder.h new file mode 100644 index 00000000000..ae30b3bba2f --- /dev/null +++ b/gcc/vector-builder.h @@ -0,0 +1,394 @@ +/* A class for building vector constant patterns. + Copyright (C) 2017 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_VECTOR_BUILDER_H +#define GCC_VECTOR_BUILDER_H + +/* This class is a wrapper around auto_vec<T> for building vectors of T. + It aims to encode each vector as npatterns interleaved patterns, + where each pattern represents a sequence: + + { BASE0, BASE1, BASE1 + STEP, BASE1 + STEP*2, BASE1 + STEP*3, ... } + + The first three elements in each pattern provide enough information + to derive the other elements. If all patterns have a STEP of zero, + we only need to encode the first two elements in each pattern. + If BASE1 is also equal to BASE0 for all patterns, we only need to + encode the first element in each pattern. The number of encoded + elements per pattern is given by nelts_per_pattern. + + The class can be used in two ways: + + 1. It can be used to build a full image of the vector, which is then + canonicalized by finalize (). In this case npatterns is initially + the number of elements in the vector and nelts_per_pattern is + initially 1. + + 2. It can be used to build a vector that already has a known encoding. + This is preferred since it is more efficient and copes with + variable-length vectors. finalize () then canonicalizes the encoding + to a simpler form if possible. + + The derived class Derived provides this functionality for specific Ts. + Derived needs to provide the following interface: + + bool equal_p (T elt1, T elt2) const; + + Return true if elements ELT1 and ELT2 are equal. + + bool allow_steps_p () const; + + Return true if a stepped representation is OK. We don't allow + linear series for anything other than integers, to avoid problems + with rounding. + + bool integral_p (T elt) const; + + Return true if element ELT can be interpreted as an integer. + + StepType step (T elt1, T elt2) const; + + Return the value of element ELT2 minus the value of element ELT1, + given integral_p (ELT1) && integral_p (ELT2). There is no fixed + choice of StepType. + + bool can_elide_p (T elt) const; + + Return true if we can drop element ELT, even if the retained + elements are different. This is provided for TREE_OVERFLOW + handling. + + void note_representative (T *elt1_ptr, T elt2); + + Record that ELT2 is being elided, given that ELT1_PTR points to + the last encoded element for the containing pattern. This is + again provided for TREE_OVERFLOW handling. */ + +template<typename T, typename Derived> +class vector_builder : public auto_vec<T, 32> +{ +public: + vector_builder (); + + unsigned int full_nelts () const { return m_full_nelts; } + unsigned int npatterns () const { return m_npatterns; } + unsigned int nelts_per_pattern () const { return m_nelts_per_pattern; } + unsigned int encoded_nelts () const; + bool encoded_full_vector_p () const; + + void finalize (); + +protected: + void new_vector (unsigned int, unsigned int, unsigned int); + void reshape (unsigned int, unsigned int); + bool repeating_sequence_p (unsigned int, unsigned int, unsigned int); + bool stepped_sequence_p (unsigned int, unsigned int, unsigned int); + bool try_npatterns (unsigned int); + +private: + vector_builder (const vector_builder &); + vector_builder &operator= (const vector_builder &); + Derived *derived () { return static_cast<Derived *> (this); } + const Derived *derived () const; + + unsigned int m_full_nelts; + unsigned int m_npatterns; + unsigned int m_nelts_per_pattern; +}; + +template<typename T, typename Derived> +inline const Derived * +vector_builder<T, Derived>::derived () const +{ + return static_cast<const Derived *> (this); +} + +template<typename T, typename Derived> +inline +vector_builder<T, Derived>::vector_builder () + : m_full_nelts (0), + m_npatterns (0), + m_nelts_per_pattern (0) +{} + +/* Return the number of elements that are explicitly encoded. The vec + starts with these explicitly-encoded elements and may contain additional + elided elements. */ + +template<typename T, typename Derived> +inline unsigned int +vector_builder<T, Derived>::encoded_nelts () const +{ + return m_npatterns * m_nelts_per_pattern; +} + +/* Return true if every element of the vector is explicitly encoded. */ + +template<typename T, typename Derived> +inline bool +vector_builder<T, Derived>::encoded_full_vector_p () const +{ + return m_npatterns * m_nelts_per_pattern == m_full_nelts; +} + +/* Start building a vector that has FULL_NELTS elements. Initially + encode it using NPATTERNS patterns with NELTS_PER_PATTERN each. */ + +template<typename T, typename Derived> +void +vector_builder<T, Derived>::new_vector (unsigned int full_nelts, + unsigned int npatterns, + unsigned int nelts_per_pattern) +{ + m_full_nelts = full_nelts; + m_npatterns = npatterns; + m_nelts_per_pattern = nelts_per_pattern; + this->reserve (encoded_nelts ()); + this->truncate (0); +} + +/* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each, + but without changing the underlying vector. */ + +template<typename T, typename Derived> +void +vector_builder<T, Derived>::reshape (unsigned int npatterns, + unsigned int nelts_per_pattern) +{ + unsigned int old_encoded_nelts = encoded_nelts (); + unsigned int new_encoded_nelts = npatterns * nelts_per_pattern; + gcc_checking_assert (new_encoded_nelts <= old_encoded_nelts); + unsigned int next = new_encoded_nelts - npatterns; + for (unsigned int i = new_encoded_nelts; i < old_encoded_nelts; ++i) + { + derived ()->note_representative (&(*this)[next], (*this)[i]); + next += 1; + if (next == new_encoded_nelts) + next -= npatterns; + } + m_npatterns = npatterns; + m_nelts_per_pattern = nelts_per_pattern; +} + +/* Return true if elements [START, END) contain a repeating sequence of + STEP elements. */ + +template<typename T, typename Derived> +bool +vector_builder<T, Derived>::repeating_sequence_p (unsigned int start, + unsigned int end, + unsigned int step) +{ + for (unsigned int i = start; i < end - step; ++i) + if (!derived ()->equal_p ((*this)[i], (*this)[i + step])) + return false; + return true; +} + +/* Return true if elements [START, END) contain STEP interleaved linear + series. */ + +template<typename T, typename Derived> +bool +vector_builder<T, Derived>::stepped_sequence_p (unsigned int start, + unsigned int end, + unsigned int step) +{ + if (!derived ()->allow_steps_p ()) + return false; + + for (unsigned int i = start + step * 2; i < end; ++i) + { + T elt1 = (*this)[i - step * 2]; + T elt2 = (*this)[i - step]; + T elt3 = (*this)[i]; + + if (!derived ()->integral_p (elt1) + || !derived ()->integral_p (elt2) + || !derived ()->integral_p (elt3)) + return false; + + if (derived ()->step (elt1, elt2) != derived ()->step (elt2, elt3)) + return false; + + if (!derived ()->can_elide_p (elt3)) + return false; + } + return true; +} + +/* Try to change the number of encoded patterns to NPATTERNS, returning + true on success. */ + +template<typename T, typename Derived> +bool +vector_builder<T, Derived>::try_npatterns (unsigned int npatterns) +{ + if (m_nelts_per_pattern == 1) + { + /* See whether NPATTERNS is valid with the current 1-element-per-pattern + encoding. */ + if (repeating_sequence_p (0, encoded_nelts (), npatterns)) + { + reshape (npatterns, 1); + return true; + } + + /* We can only increase the number of elements per pattern if all + elements are still encoded explicitly. */ + if (!encoded_full_vector_p ()) + return false; + } + + if (m_nelts_per_pattern <= 2) + { + /* See whether NPATTERNS is valid with a 2-element-per-pattern + encoding. */ + if (repeating_sequence_p (npatterns, encoded_nelts (), npatterns)) + { + reshape (npatterns, 2); + return true; + } + + /* We can only increase the number of elements per pattern if all + elements are still encoded explicitly. */ + if (!encoded_full_vector_p ()) + return false; + } + + if (m_nelts_per_pattern <= 3) + { + /* See whether we have NPATTERNS interleaved linear series, + giving a 3-element-per-pattern encoding. */ + if (stepped_sequence_p (npatterns, encoded_nelts (), npatterns)) + { + reshape (npatterns, 3); + return true; + } + return false; + } + + gcc_unreachable (); +} + +/* Replace the current encoding with the canonical form. */ + +template<typename T, typename Derived> +void +vector_builder<T, Derived>::finalize () +{ + /* The encoding requires the same number of elements to come from each + pattern. */ + gcc_assert (m_full_nelts % m_npatterns == 0); + + /* Allow the caller to build more elements than necessary. For example, + it's often convenient to build a stepped vector from the natural + encoding of three elements even if the vector itself only has two. */ + if (m_full_nelts <= encoded_nelts ()) + { + m_npatterns = m_full_nelts; + m_nelts_per_pattern = 1; + } + + /* Try to whittle down the number of elements per pattern. That is: + + 1. If we have stepped patterns whose steps are all 0, reduce the + number of elements per pattern from 3 to 2. + + 2. If we have background fill values that are the same as the + foreground values, reduce the number of elements per pattern + from 2 to 1. */ + while (m_nelts_per_pattern > 1 + && repeating_sequence_p (encoded_nelts () - m_npatterns * 2, + encoded_nelts (), m_npatterns)) + /* The last two sequences of M_NPATTERNS elements are equal, + so remove the last one. */ + reshape (m_npatterns, m_nelts_per_pattern - 1); + + if (pow2p_hwi (m_npatterns)) + { + /* Try to halve the number of patterns while doing so gives a + valid pattern. This approach is linear in the number of + elements, whereas searcing from 1 up would be O(n*log(n)). + + Each halving step tries to keep the number of elements per pattern + the same. If that isn't possible, and if all elements are still + explicitly encoded, the halving step can instead increase the number + of elements per pattern. + + E.g. for: + + { 0, 2, 3, 4, 5, 6, 7, 8 } npatterns == 8 full_nelts == 8 + + we first realize that the second half of the sequence is not + equal to the first, so we cannot maintain 1 element per pattern + for npatterns == 4. Instead we halve the number of patterns + and double the number of elements per pattern, treating this + as a "foreground" { 0, 2, 3, 4 } against a "background" of + { 5, 6, 7, 8 | 5, 6, 7, 8 ... }: + + { 0, 2, 3, 4 | 5, 6, 7, 8 } npatterns == 4 + + Next we realize that this is *not* a foreround of { 0, 2 } + against a background of { 3, 4 | 3, 4 ... }, so the only + remaining option for reducing the number of patterns is + to use a foreground of { 0, 2 } against a stepped background + of { 1, 2 | 3, 4 | 5, 6 ... }. This is valid because we still + haven't elided any elements: + + { 0, 2 | 3, 4 | 5, 6 } npatterns == 2 + + This in turn can be reduced to a foreground of { 0 } against a + stepped background of { 1 | 2 | 3 ... }: + + { 0 | 2 | 3 } npatterns == 1 + + This last step would not have been possible for: + + { 0, 0 | 3, 4 | 5, 6 } npatterns == 2. */ + while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2)) + continue; + + /* Builders of arbitrary fixed-length vectors can use: + + new_vector (x, x, 1) + + so that every element is specified explicitly. Handle cases + that are actually wrapping series, like { 0, 1, 2, 3, 0, 1, 2, 3 } + would be for 2-bit elements. We'll have treated them as + duplicates in the loop above. */ + if (m_nelts_per_pattern == 1 + && this->length () >= m_full_nelts + && (m_npatterns & 3) == 0 + && stepped_sequence_p (m_npatterns / 4, m_full_nelts, + m_npatterns / 4)) + { + reshape (m_npatterns / 4, 3); + while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2)) + continue; + } + } + else + /* For the non-power-of-2 case, do a simple search up from 1. */ + for (unsigned int i = 1; i <= m_npatterns / 2; ++i) + if (m_npatterns % i == 0 && try_npatterns (i)) + break; +} + +#endif |