New VECTOR_CST layout

This patch uses a simple compression scheme to represent the contents
of a VECTOR_CST using its leading elements.  There are three formats:

1) a repeating sequence of N values.  This is encoded using the first
   N elements.

2) a "foreground" sequence of N values inserted at the beginning of
   a "background" repeating sequence of N values, such as:
   { 1, 2, 0, 0, 0, 0, ... }.  This is encoded using the first 2*N
   elements.

2) a "foreground" sequence of N values inserted at the beginning of
   a "background" repeating sequence of N interleaved linear series,
   such as: { 0, 0, 8, 10, 9, 11, 10, 12, ... }.  This is encoded
   using the first 3*N elements.  In practice the foreground values
   are often part of the same series as the background values,
   such as: { 1, 11, 2, 12, 3, 13, ... }.

This reduces the amount of work involved in processing simple
vector constants and means that the encoding extends naturally
to variable-length vectors.

2017-12-07  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* 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.

gcc/lto/
	* lto.c (compare_tree_sccs_1): Compare the new VECTOR_CST flags.

From-SVN: r255474

1 files changed, 30 insertions, 5 deletions

diff --git a/gcc/tree.h b/gcc/tree.h
index e5a37af..b3cf747 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.  */