This patch changes TYPE_VECTOR_SUBPARTS to a poly_uint64.  The value is
encoded in the 10-bit precision field and was previously always stored
as a simple log2 value.  The challenge was to use this 10 bits to
encode the number of elements in variable-length vectors, so that
we didn't need to increase the size of the tree.

In practice the number of vector elements should always have the form
N + N * X (where X is the runtime value), and as for constant-length
vectors, N must be a power of 2 (even though X itself might not be).
The patch therefore uses the low 8 bits to encode log2(N) and bit
8 to select between constant-length and variable-length vectors.
Targets without variable-length vectors continue to use the old scheme.

A new valid_vector_subparts_p function tests whether a given number
of elements can be encoded.  This is false for the vector modes that
represent an LD3 or ST3 vector triple (which we want to treat as arrays
of vectors rather than single vectors).

Most of the patch is mechanical; previous patches handled the changes
that weren't entirely straightforward.

2018-01-03  Richard Sandiford  <richard.sandiford@linaro.org>
	    Alan Hayward  <alan.hayward@arm.com>
	    David Sherwood  <david.sherwood@arm.com>

gcc/
	* tree.h (TYPE_VECTOR_SUBPARTS): Turn into a function and handle
	polynomial numbers of units.
	(SET_TYPE_VECTOR_SUBPARTS): Likewise.
	(valid_vector_subparts_p): New function.
	(build_vector_type): Remove temporary shim and take the number
	of units as a poly_uint64 rather than an int.
	(build_opaque_vector_type): Take the number of units as a
	poly_uint64 rather than an int.
	* tree.c (build_vector_from_ctor): Handle polynomial
	TYPE_VECTOR_SUBPARTS.
	(type_hash_canon_hash, type_cache_hasher::equal): Likewise.
	(uniform_vector_p, vector_type_mode, build_vector): Likewise.
	(build_vector_from_val): If the number of units is variable,
	use build_vec_duplicate_cst for constant operands and
	VEC_DUPLICATE_EXPR otherwise.
	(make_vector_type): Remove temporary is_constant ().
	(build_vector_type, build_opaque_vector_type): Take the number of
	units as a poly_uint64 rather than an int.
	(check_vector_cst): Handle polynomial TYPE_VECTOR_SUBPARTS and
	VECTOR_CST_NELTS.
	* cfgexpand.c (expand_debug_expr): Likewise.
	* expr.c (count_type_elements, categorize_ctor_elements_1): Likewise.
	(store_constructor, expand_expr_real_1): Likewise.
	(const_scalar_mask_from_tree): Likewise.
	* fold-const-call.c (fold_const_reduction): Likewise.
	* fold-const.c (const_binop, const_unop, fold_convert_const): Likewise.
	(operand_equal_p, fold_vec_perm, fold_ternary_loc): Likewise.
	(native_encode_vector, vec_cst_ctor_to_array): Likewise.
	(fold_relational_const): Likewise.
	(native_interpret_vector): Likewise.  Change the size from an
	int to an unsigned int.
	* gimple-fold.c (gimple_fold_stmt_to_constant_1): Handle polynomial
	TYPE_VECTOR_SUBPARTS.
	(gimple_fold_indirect_ref, gimple_build_vector): Likewise.
	(gimple_build_vector_from_val): Use VEC_DUPLICATE_EXPR when
	duplicating a non-constant operand into a variable-length vector.
	* hsa-brig.c (hsa_op_immed::emit_to_buffer): Handle polynomial
	TYPE_VECTOR_SUBPARTS and VECTOR_CST_NELTS.
	* ipa-icf.c (sem_variable::equals): Likewise.
	* match.pd: Likewise.
	* omp-simd-clone.c (simd_clone_subparts): Likewise.
	* print-tree.c (print_node): Likewise.
	* stor-layout.c (layout_type): Likewise.
	* targhooks.c (default_builtin_vectorization_cost): Likewise.
	* tree-cfg.c (verify_gimple_comparison): Likewise.
	(verify_gimple_assign_binary): Likewise.
	(verify_gimple_assign_ternary): Likewise.
	(verify_gimple_assign_single): Likewise.
	* tree-pretty-print.c (dump_generic_node): Likewise.
	* tree-ssa-forwprop.c (simplify_vector_constructor): Likewise.
	(simplify_bitfield_ref, is_combined_permutation_identity): Likewise.
	* tree-vect-data-refs.c (vect_permute_store_chain): Likewise.
	(vect_grouped_load_supported, vect_permute_load_chain): Likewise.
	(vect_shift_permute_load_chain): Likewise.
	* tree-vect-generic.c (nunits_for_known_piecewise_op): Likewise.
	(expand_vector_condition, optimize_vector_constructor): Likewise.
	(lower_vec_perm, get_compute_type): Likewise.
	* tree-vect-loop.c (vect_determine_vectorization_factor): Likewise.
	(get_initial_defs_for_reduction, vect_transform_loop): Likewise.
	* tree-vect-patterns.c (vect_recog_bool_pattern): Likewise.
	(vect_recog_mask_conversion_pattern): Likewise.
	* tree-vect-slp.c (vect_supported_load_permutation_p): Likewise.
	(vect_get_constant_vectors, vect_transform_slp_perm_load): Likewise.
	* tree-vect-stmts.c (perm_mask_for_reverse): Likewise.
	(get_group_load_store_type, vectorizable_mask_load_store): Likewise.
	(vectorizable_bswap, simd_clone_subparts, vectorizable_assignment)
	(vectorizable_shift, vectorizable_operation, vectorizable_store)
	(vectorizable_load, vect_is_simple_cond, vectorizable_comparison)
	(supportable_widening_operation): Likewise.
	(supportable_narrowing_operation): Likewise.
	* tree-vector-builder.c (tree_vector_builder::binary_encoded_nelts):
	Likewise.
	* varasm.c (output_constant): Likewise.

gcc/ada/
	* gcc-interface/utils.c (gnat_types_compatible_p): Handle
	polynomial TYPE_VECTOR_SUBPARTS.

gcc/brig/
	* brigfrontend/brig-to-generic.cc (get_unsigned_int_type): Handle
	polynomial TYPE_VECTOR_SUBPARTS.
	* brigfrontend/brig-util.h (gccbrig_type_vector_subparts): Likewise.

gcc/c-family/
	* c-common.c (vector_types_convertible_p, c_build_vec_perm_expr)
	(convert_vector_to_array_for_subscript): Handle polynomial
	TYPE_VECTOR_SUBPARTS.
	(c_common_type_for_mode): Check valid_vector_subparts_p.
	* c-pretty-print.c (pp_c_initializer_list): Handle polynomial
	VECTOR_CST_NELTS.

gcc/c/
	* c-typeck.c (comptypes_internal, build_binary_op): Handle polynomial
	TYPE_VECTOR_SUBPARTS.

gcc/cp/
	* constexpr.c (cxx_eval_array_reference): Handle polynomial
	VECTOR_CST_NELTS.
	(cxx_fold_indirect_ref): Handle polynomial TYPE_VECTOR_SUBPARTS.
	* call.c (build_conditional_expr_1): Likewise.
	* decl.c (cp_finish_decomp): Likewise.
	* mangle.c (write_type): Likewise.
	* typeck.c (structural_comptypes): Likewise.
	(cp_build_binary_op): Likewise.
	* typeck2.c (process_init_constructor_array): Likewise.

gcc/fortran/
	* trans-types.c (gfc_type_for_mode): Check valid_vector_subparts_p.

gcc/lto/
	* lto-lang.c (lto_type_for_mode): Check valid_vector_subparts_p.
	* lto.c (hash_canonical_type): Handle polynomial TYPE_VECTOR_SUBPARTS.

gcc/go/
	* go-lang.c (go_langhook_type_for_mode): Check valid_vector_subparts_p.

Co-Authored-By: Alan Hayward <alan.hayward@arm.com>
Co-Authored-By: David Sherwood <david.sherwood@arm.com>

From-SVN: r256197

From-SVN: r256169

This patch changes the number of elements in a vector being built
by a vector_builder from unsigned int to poly_uint64.  The case
in which it isn't a constant is the one that motivated adding
the vector encoding in the first place.

2018-01-03  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	* vector-builder.h (vector_builder::m_full_nelts): Change from
	unsigned int to poly_uint64.
	(vector_builder::full_nelts): Update prototype accordingly.
	(vector_builder::new_vector): Likewise.
	(vector_builder::encoded_full_vector_p): Handle polynomial full_nelts.
	(vector_builder::operator ==): Likewise.
	(vector_builder::finalize): Likewise.
	* int-vector-builder.h (int_vector_builder::int_vector_builder):
	Take the number of elements as a poly_uint64 rather than an
	unsigned int.
	* vec-perm-indices.h (vec_perm_indices::m_nelts_per_input): Change
	from unsigned int to poly_uint64.
	(vec_perm_indices::vec_perm_indices): Update prototype accordingly.
	(vec_perm_indices::new_vector): Likewise.
	(vec_perm_indices::length): Likewise.
	(vec_perm_indices::nelts_per_input): Likewise.
	(vec_perm_indices::input_nelts): Likewise.
	* vec-perm-indices.c (vec_perm_indices::new_vector): Take the
	number of elements per input as a poly_uint64 rather than an
	unsigned int.  Use the original encoding for variable-length
	vectors, rather than clamping each individual element.
	For the second and subsequent elements in each pattern,
	clamp the step and base before clamping their sum.
	(vec_perm_indices::series_p): Handle polynomial element counts.
	(vec_perm_indices::all_in_range_p): Likewise.
	(vec_perm_indices_to_tree): Likewise.
	(vec_perm_indices_to_rtx): Likewise.
	* tree-vect-stmts.c (vect_gen_perm_mask_any): Likewise.
	* tree-vector-builder.c (tree_vector_builder::new_unary_operation)
	(tree_vector_builder::new_binary_operation): Handle polynomial
	element counts.  Return false if we need to know the number
	of elements at compile time.
	* fold-const.c (fold_vec_perm): Punt if the number of elements
	isn't known at compile time.

From-SVN: r256165

This patch makes various bits of code operate directly on the new
VECTOR_CST encoding, instead of using VECTOR_CST_ELT on all elements
of the vector.

Previous patches handled operations that produce a new VECTOR_CST,
while this patch handles things like predicates.  It also makes
print_node dump the encoding instead of the full vector that
the encoding represents.

2017-12-07  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	* tree-vector-builder.h
	(tree_vector_builder::binary_encoded_nelts): Declare.
	* tree-vector-builder.c
	(tree_vector_builder::binary_encoded_nelts): New function.
	* fold-const.c (negate_expr_p): Likewise.
	(operand_equal_p, fold_checksum_tree): Likewise.
	* tree-loop-distribution.c (const_with_all_bytes_same): Likewise.
	* tree.c (integer_zerop, integer_onep, integer_all_onesp, real_zerop)
	(real_onep, real_minus_onep, add_expr, initializer_zerop): Likewise.
	(uniform_vector_p): Likewise.
	* varasm.c (const_hash_1, compare_constant): Likewise.
	* tree-ssa-ccp.c: Include tree-vector-builder.h.
	(valid_lattice_transition): Operate directly on the VECTOR_CST
	encoding.
	* ipa-icf.c: Include tree-vector-builder.h.
	(sem_variable::equals): Operate directly on the VECTOR_CST encoding.
	* print-tree.c (print_node): Print encoding of VECTOR_CSTs.

From-SVN: r255480

This patch changes gimple_build_vector so that it takes a
tree_vector_builder instead of a size and a vector of trees.

2017-12-07  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	* vector-builder.h (vector_builder::derived): New const overload.
	(vector_builder::elt): New function.
	* tree-vector-builder.h (tree_vector_builder::type): New function.
	(tree_vector_builder::apply_step): Declare.
	* tree-vector-builder.c (tree_vector_builder::apply_step): New
	function.
	* gimple-fold.h (tree_vector_builder): Declare.
	(gimple_build_vector): Take a tree_vector_builder instead of a
	type and vector of elements.
	* gimple-fold.c (gimple_build_vector): Likewise.
	* tree-vect-loop.c (get_initial_def_for_reduction): Update call
	accordingly.
	(get_initial_defs_for_reduction): Likewise.
	(vectorizable_induction): Likewise.

From-SVN: r255478

This patch makes fold-const.c operate directly on the VECTOR_CST
encoding when folding an operation that has two VECTOR_CST inputs.

2017-12-07  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	* tree-vector-builder.h
	(tree_vector_builder::new_binary_operation): Declare.
	* tree-vector-builder.c
	(tree_vector_builder::new_binary_operation): New function.
	* fold-const.c (fold_relational_const): Use it.
	(const_binop): Likewise.  Check that both input vectors have
	the same number of elements, thus excluding things like WIDEN_SUM.
	Check whether it is possible to operate directly on the encodings
	of stepped inputs.

From-SVN: r255477

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