Add support for fully-predicated loops

Add support for fully-predicated loops

This patch adds support for using a single fully-predicated loop instead
of a vector loop and a scalar tail.  An SVE WHILELO instruction generates
the predicate for each iteration of the loop, given the current scalar
iv value and the loop bound.  This operation is wrapped up in a new internal
function called WHILE_ULT.  E.g.:

   WHILE_ULT (0, 3, { 0, 0, 0, 0}) -> { 1, 1, 1, 0 }
   WHILE_ULT (UINT_MAX - 1, UINT_MAX, { 0, 0, 0, 0 }) -> { 1, 0, 0, 0 }

The third WHILE_ULT argument is needed to make the operation
unambiguous: without it, WHILE_ULT (0, 3) for one vector type would
seem equivalent to WHILE_ULT (0, 3) for another, even if the types have
different numbers of elements.

Note that the patch uses "mask" and "fully-masked" instead of
"predicate" and "fully-predicated", to follow existing GCC terminology.

This patch just handles the simple cases, punting for things like
reductions and live-out values.  Later patches remove most of these
restrictions.

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

gcc/
	* optabs.def (while_ult_optab): New optab.
	* doc/md.texi (while_ult@var{m}@var{n}): Document.
	* internal-fn.def (WHILE_ULT): New internal function.
	* internal-fn.h (direct_internal_fn_supported_p): New override
	that takes two types as argument.
	* internal-fn.c (while_direct): New macro.
	(expand_while_optab_fn): New function.
	(convert_optab_supported_p): Likewise.
	(direct_while_optab_supported_p): New macro.
	* wide-int.h (wi::udiv_ceil): New function.
	* tree-vectorizer.h (rgroup_masks): New structure.
	(vec_loop_masks): New typedef.
	(_loop_vec_info): Add masks, mask_compare_type, can_fully_mask_p
	and fully_masked_p.
	(LOOP_VINFO_CAN_FULLY_MASK_P, LOOP_VINFO_FULLY_MASKED_P)
	(LOOP_VINFO_MASKS, LOOP_VINFO_MASK_COMPARE_TYPE): New macros.
	(vect_max_vf): New function.
	(slpeel_make_loop_iterate_ntimes): Delete.
	(vect_set_loop_condition, vect_get_loop_mask_type, vect_gen_while)
	(vect_halve_mask_nunits, vect_double_mask_nunits): Declare.
	(vect_record_loop_mask, vect_get_loop_mask): Likewise.
	* tree-vect-loop-manip.c: Include tree-ssa-loop-niter.h,
	internal-fn.h, stor-layout.h and optabs-query.h.
	(vect_set_loop_mask): New function.
	(add_preheader_seq): Likewise.
	(add_header_seq): Likewise.
	(interleave_supported_p): Likewise.
	(vect_maybe_permute_loop_masks): Likewise.
	(vect_set_loop_masks_directly): Likewise.
	(vect_set_loop_condition_masked): Likewise.
	(vect_set_loop_condition_unmasked): New function, split out from
	slpeel_make_loop_iterate_ntimes.
	(slpeel_make_loop_iterate_ntimes): Rename to..
	(vect_set_loop_condition): ...this.  Use vect_set_loop_condition_masked
	for fully-masked loops and vect_set_loop_condition_unmasked otherwise.
	(vect_do_peeling): Update call accordingly.
	(vect_gen_vector_loop_niters): Use VF as the step for fully-masked
	loops.
	* tree-vect-loop.c (_loop_vec_info::_loop_vec_info): Initialize
	mask_compare_type, can_fully_mask_p and fully_masked_p.
	(release_vec_loop_masks): New function.
	(_loop_vec_info): Use it to free the loop masks.
	(can_produce_all_loop_masks_p): New function.
	(vect_get_max_nscalars_per_iter): Likewise.
	(vect_verify_full_masking): Likewise.
	(vect_analyze_loop_2): Save LOOP_VINFO_CAN_FULLY_MASK_P around
	retries, and free the mask rgroups before retrying.  Check loop-wide
	reasons for disallowing fully-masked loops.  Make the final decision
	about whether use a fully-masked loop or not.
	(vect_estimate_min_profitable_iters): Do not assume that peeling
	for the number of iterations will be needed for fully-masked loops.
	(vectorizable_reduction): Disable fully-masked loops.
	(vectorizable_live_operation): Likewise.
	(vect_halve_mask_nunits): New function.
	(vect_double_mask_nunits): Likewise.
	(vect_record_loop_mask): Likewise.
	(vect_get_loop_mask): Likewise.
	(vect_transform_loop): Handle the case in which the final loop
	iteration might handle a partial vector.  Call vect_set_loop_condition
	instead of slpeel_make_loop_iterate_ntimes.
	* tree-vect-stmts.c: Include tree-ssa-loop-niter.h and gimple-fold.h.
	(check_load_store_masking): New function.
	(prepare_load_store_mask): Likewise.
	(vectorizable_store): Handle fully-masked loops.
	(vectorizable_load): Likewise.
	(supportable_widening_operation): Use vect_halve_mask_nunits for
	booleans.
	(supportable_narrowing_operation): Likewise vect_double_mask_nunits.
	(vect_gen_while): New function.
	* config/aarch64/aarch64.md (umax<mode>3): New expander.
	(aarch64_uqdec<mode>): New insn.

gcc/testsuite/
	* gcc.dg/tree-ssa/cunroll-10.c: Disable vectorization.
	* gcc.dg/tree-ssa/peel1.c: Likewise.
	* gcc.dg/vect/vect-load-lanes-peeling-1.c: Remove XFAIL for
	variable-length vectors.
	* gcc.target/aarch64/sve/vcond_6.c: XFAIL test for AND.
	* gcc.target/aarch64/sve/vec_bool_cmp_1.c: Expect BIC instead of NOT.
	* gcc.target/aarch64/sve/slp_1.c: Check for a fully-masked loop.
	* gcc.target/aarch64/sve/slp_2.c: Likewise.
	* gcc.target/aarch64/sve/slp_3.c: Likewise.
	* gcc.target/aarch64/sve/slp_4.c: Likewise.
	* gcc.target/aarch64/sve/slp_6.c: Likewise.
	* gcc.target/aarch64/sve/slp_8.c: New test.
	* gcc.target/aarch64/sve/slp_8_run.c: Likewise.
	* gcc.target/aarch64/sve/slp_9.c: Likewise.
	* gcc.target/aarch64/sve/slp_9_run.c: Likewise.
	* gcc.target/aarch64/sve/slp_10.c: Likewise.
	* gcc.target/aarch64/sve/slp_10_run.c: Likewise.
	* gcc.target/aarch64/sve/slp_11.c: Likewise.
	* gcc.target/aarch64/sve/slp_11_run.c: Likewise.
	* gcc.target/aarch64/sve/slp_12.c: Likewise.
	* gcc.target/aarch64/sve/slp_12_run.c: Likewise.
	* gcc.target/aarch64/sve/ld1r_2.c: Likewise.
	* gcc.target/aarch64/sve/ld1r_2_run.c: Likewise.
	* gcc.target/aarch64/sve/while_1.c: Likewise.
	* gcc.target/aarch64/sve/while_2.c: Likewise.
	* gcc.target/aarch64/sve/while_3.c: Likewise.
	* gcc.target/aarch64/sve/while_4.c: Likewise.

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