[PATCH] Use get_nonzero_bits to improve vectorization
Richard Biener
rguenther@suse.de
Tue Oct 29 12:18:00 GMT 2013
On Fri, 25 Oct 2013, Jakub Jelinek wrote:
> Hi!
>
> The following patch makes use of the computed nonzero_bits preserved
> in the SSA_NAME_RANGE_INFO.
> I chose to write a new routine instead of improving current
> highest_pow2_factor, because that routine didn't care about overflows etc.
> and by working on ctz numbers instead of powers of two in UHWI we can handle
> even larger constants etc. highest_pow2_factor could very well overflow to
> zero etc. So, the patch introduces a new tree_ctz routine and reimplements
> highest_pow2_factor on top of that, plus uses tree_ctz also in
> get_object_alignment_2 and in the vectorizer to determine if it can avoid
> scalar loop for bound (and indirectly also in the analysis whether peeling
> for alignment is needed).
>
> With this patch, e.g.
> int a[1024];
>
> void
> foo (int x, int y)
> {
> int i;
> x &= -32;
> y &= -32;
> for (i = x + 32; i < y; i++)
> a[i]++;
> }
> can be vectorized without any peeling for alignment or scalar loop
> afterwards.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
>
> 2013-10-25 Jakub Jelinek <jakub@redhat.com>
>
> * tree.c (tree_ctz): New function.
> * tree.h (tree_ctz): New prototype.
> * tree-ssanames.h (get_range_info, get_nonzero_bits): Change
> first argument from tree to const_tree.
> * tree-ssanames.c (get_range_info, get_nonzero_bits): Likewise.
> * tree-vectorizer.h (vect_generate_tmps_on_preheader): New prototype.
> * tree-vect-loop-manip.c (vect_generate_tmps_on_preheader): No longer
> static.
> * expr.c (highest_pow2_factor): Reimplemented using tree_ctz.
> * tree-vect-loop.c (vect_analyze_loop_operations,
> vect_transform_loop): Don't force scalar loop for bound just because
> number of iterations is unknown, only do it if it is not known to be
> a multiple of vectorization_factor.
> * builtins.c (get_object_alignment_2): Use tree_ctz on offset.
>
> --- gcc/tree.c.jj 2013-10-23 14:43:12.000000000 +0200
> +++ gcc/tree.c 2013-10-25 15:00:55.296178794 +0200
> @@ -2213,6 +2213,110 @@ tree_floor_log2 (const_tree expr)
> : floor_log2 (low));
> }
>
> +/* Return number of known trailing zero bits in EXPR, or, if the value of
> + EXPR is known to be zero, the precision of it's type. */
> +
> +int
unsigned int?
> +tree_ctz (const_tree expr)
> +{
> + if (!INTEGRAL_TYPE_P (TREE_TYPE (expr))
> + && !POINTER_TYPE_P (TREE_TYPE (expr)))
> + return 0;
> +
> + int ret1, ret2, prec = TYPE_PRECISION (TREE_TYPE (expr));
> + switch (TREE_CODE (expr))
> + {
> + case INTEGER_CST:
> + ret1 = tree_to_double_int (expr).trailing_zeros ();
> + return MIN (ret1, prec);
> + case SSA_NAME:
> + ret1 = get_nonzero_bits (expr).trailing_zeros ();
> + return MIN (ret1, prec);
> + case PLUS_EXPR:
> + case MINUS_EXPR:
> + case BIT_IOR_EXPR:
> + case BIT_XOR_EXPR:
> + case MIN_EXPR:
> + case MAX_EXPR:
> + ret1 = tree_ctz (TREE_OPERAND (expr, 0));
> + ret2 = tree_ctz (TREE_OPERAND (expr, 1));
This first recurses but if either one returns 0 you don't have
to (that cuts down the recursion from exponential to linear in
the common case?). Thus, early out on ret == 0?
> + return MIN (ret1, ret2);
> + case POINTER_PLUS_EXPR:
> + ret1 = tree_ctz (TREE_OPERAND (expr, 0));
> + ret2 = tree_ctz (TREE_OPERAND (expr, 1));
> + ret2 = MIN (ret2, prec);
Why do you need that here but not elsewhere when processing
binary ops?
> + return MIN (ret1, ret2);
> + case BIT_AND_EXPR:
> + ret1 = tree_ctz (TREE_OPERAND (expr, 0));
> + ret2 = tree_ctz (TREE_OPERAND (expr, 1));
> + return MAX (ret1, ret2);
> + case MULT_EXPR:
> + ret1 = tree_ctz (TREE_OPERAND (expr, 0));
> + ret2 = tree_ctz (TREE_OPERAND (expr, 1));
> + return MIN (ret1 + ret2, prec);
> + case LSHIFT_EXPR:
> + ret1 = tree_ctz (TREE_OPERAND (expr, 0));
> + if (host_integerp (TREE_OPERAND (expr, 1), 1)
check that first before recursing for op0 - if op1 is negative
you simply return ret1 which looks wrong, too.
> + && ((unsigned HOST_WIDE_INT) tree_low_cst (TREE_OPERAND (expr, 1), 1)
> + < (unsigned HOST_WIDE_INT) prec))
This check is to avoid overflowing ret1 + ret2? If so, why not add
> + {
> + ret2 = tree_low_cst (TREE_OPERAND (expr, 1), 1);
ret2 = MIN (ret2, prec);
instead?
> + return MIN (ret1 + ret2, prec);
> + }
> + return ret1;
> + case RSHIFT_EXPR:
> + if (host_integerp (TREE_OPERAND (expr, 1), 1)
> + && ((unsigned HOST_WIDE_INT) tree_low_cst (TREE_OPERAND (expr, 1), 1)
> + < (unsigned HOST_WIDE_INT) prec))
> + {
> + ret1 = tree_ctz (TREE_OPERAND (expr, 0));
> + ret2 = tree_low_cst (TREE_OPERAND (expr, 1), 1);
> + if (ret1 > ret2)
> + return ret1 - ret2;
> + }
> + return 0;
Seems to be slightly better structured. Looks like you assume only
positive shift amounts exist in the LSHIFT_EXPR case, I'm not sure
that's a valid assumption (see constant folding code dealing with that).
> + case TRUNC_DIV_EXPR:
> + case CEIL_DIV_EXPR:
> + case FLOOR_DIV_EXPR:
> + case ROUND_DIV_EXPR:
> + case EXACT_DIV_EXPR:
> + if (TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST)
> + {
> + ret2 = tree_log2 (TREE_OPERAND (expr, 1));
> + if (ret2 >= 0 && tree_int_cst_sgn (TREE_OPERAND (expr, 1)) == 1)
cheaper to test the sign first.
> + {
> + ret1 = tree_ctz (TREE_OPERAND (expr, 0));
> + if (ret1 > ret2)
> + return ret1 - ret2;
> + }
> + }
> + return 0;
> + CASE_CONVERT:
> + ret1 = tree_ctz (TREE_OPERAND (expr, 0));
> + if (ret1 && ret1 == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (expr, 0))))
> + ret1 = prec;
> + return MIN (ret1, prec);
> + case SAVE_EXPR:
> + return tree_ctz (TREE_OPERAND (expr, 0));
> + case COND_EXPR:
> + ret1 = tree_ctz (TREE_OPERAND (expr, 1));
> + ret2 = tree_ctz (TREE_OPERAND (expr, 2));
> + return MIN (ret1, ret2);
> + case COMPOUND_EXPR:
> + return tree_ctz (TREE_OPERAND (expr, 1));
> + case ADDR_EXPR:
> + ret1 = get_object_alignment (TREE_OPERAND (expr, 0));
Use get_pointer_alignment, this isn't a memory reference so type
alignment rules don't apply.
The rest looks ok to me.
Thanks,
Richard.
> + if (ret1 > BITS_PER_UNIT)
> + {
> + ret1 = ctz_hwi (ret1 / BITS_PER_UNIT);
> + return MIN (ret1, prec);
> + }
> + return 0;
> + default:
> + return 0;
> + }
> +}
> +
> /* Return 1 if EXPR is the real constant zero. Trailing zeroes matter for
> decimal float constants, so don't return 1 for them. */
>
> --- gcc/tree.h.jj 2013-10-17 22:30:45.000000000 +0200
> +++ gcc/tree.h 2013-10-25 12:20:05.473673186 +0200
> @@ -4546,6 +4546,7 @@ extern void get_type_static_bounds (cons
> extern bool variably_modified_type_p (tree, tree);
> extern int tree_log2 (const_tree);
> extern int tree_floor_log2 (const_tree);
> +extern int tree_ctz (const_tree);
> extern int simple_cst_equal (const_tree, const_tree);
> extern hashval_t iterative_hash_expr (const_tree, hashval_t);
> extern hashval_t iterative_hash_exprs_commutative (const_tree,
> --- gcc/tree-ssanames.h.jj 2013-10-24 15:52:53.000000000 +0200
> +++ gcc/tree-ssanames.h 2013-10-25 14:09:21.227015919 +0200
> @@ -72,9 +72,10 @@ enum value_range_type { VR_UNDEFINED, VR
> /* Sets the value range to SSA. */
> extern void set_range_info (tree, double_int, double_int);
> /* Gets the value range from SSA. */
> -extern enum value_range_type get_range_info (tree, double_int *, double_int *);
> +extern enum value_range_type get_range_info (const_tree, double_int *,
> + double_int *);
> extern void set_nonzero_bits (tree, double_int);
> -extern double_int get_nonzero_bits (tree);
> +extern double_int get_nonzero_bits (const_tree);
> extern void init_ssanames (struct function *, int);
> extern void fini_ssanames (void);
> extern void ssanames_print_statistics (void);
> --- gcc/tree-ssanames.c.jj 2013-10-24 17:32:22.000000000 +0200
> +++ gcc/tree-ssanames.c 2013-10-25 14:08:46.218187581 +0200
> @@ -221,7 +221,7 @@ set_range_info (tree name, double_int mi
> is used to determine if MIN and MAX are valid values. */
>
> enum value_range_type
> -get_range_info (tree name, double_int *min, double_int *max)
> +get_range_info (const_tree name, double_int *min, double_int *max)
> {
> enum value_range_type range_type;
> gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
> @@ -271,7 +271,7 @@ set_nonzero_bits (tree name, double_int
> NAME, or double_int_minus_one if unknown. */
>
> double_int
> -get_nonzero_bits (tree name)
> +get_nonzero_bits (const_tree name)
> {
> if (POINTER_TYPE_P (TREE_TYPE (name)))
> {
> --- gcc/tree-vectorizer.h.jj 2013-10-24 10:19:20.000000000 +0200
> +++ gcc/tree-vectorizer.h 2013-10-25 14:02:58.198999063 +0200
> @@ -901,6 +901,8 @@ extern void slpeel_make_loop_iterate_nti
> extern bool slpeel_can_duplicate_loop_p (const struct loop *, const_edge);
> struct loop *slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *, edge);
> extern void vect_loop_versioning (loop_vec_info, unsigned int, bool);
> +extern void vect_generate_tmps_on_preheader (loop_vec_info, tree *, tree *,
> + tree *, gimple_seq);
> extern void vect_do_peeling_for_loop_bound (loop_vec_info, tree *,
> unsigned int, bool);
> extern void vect_do_peeling_for_alignment (loop_vec_info, unsigned int, bool);
> --- gcc/tree-vect-loop-manip.c.jj 2013-10-24 10:19:22.000000000 +0200
> +++ gcc/tree-vect-loop-manip.c 2013-10-25 14:02:00.544284058 +0200
> @@ -1437,7 +1437,7 @@ vect_build_loop_niters (loop_vec_info lo
> and places them at the loop preheader edge or in COND_EXPR_STMT_LIST
> if that is non-NULL. */
>
> -static void
> +void
> vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo,
> tree *ni_name_ptr,
> tree *ratio_mult_vf_name_ptr,
> --- gcc/expr.c.jj 2013-10-23 14:43:15.000000000 +0200
> +++ gcc/expr.c 2013-10-25 15:05:23.893781676 +0200
> @@ -7282,74 +7282,14 @@ safe_from_p (const_rtx x, tree exp, int
> unsigned HOST_WIDE_INT
> highest_pow2_factor (const_tree exp)
> {
> - unsigned HOST_WIDE_INT c0, c1;
> -
> - switch (TREE_CODE (exp))
> - {
> - case INTEGER_CST:
> - /* We can find the lowest bit that's a one. If the low
> - HOST_BITS_PER_WIDE_INT bits are zero, return BIGGEST_ALIGNMENT.
> - We need to handle this case since we can find it in a COND_EXPR,
> - a MIN_EXPR, or a MAX_EXPR. If the constant overflows, we have an
> - erroneous program, so return BIGGEST_ALIGNMENT to avoid any
> - later ICE. */
> - if (TREE_OVERFLOW (exp))
> - return BIGGEST_ALIGNMENT;
> - else
> - {
> - /* Note: tree_low_cst is intentionally not used here,
> - we don't care about the upper bits. */
> - c0 = TREE_INT_CST_LOW (exp);
> - c0 &= -c0;
> - return c0 ? c0 : BIGGEST_ALIGNMENT;
> - }
> - break;
> -
> - case PLUS_EXPR: case MINUS_EXPR: case MIN_EXPR: case MAX_EXPR:
> - c0 = highest_pow2_factor (TREE_OPERAND (exp, 0));
> - c1 = highest_pow2_factor (TREE_OPERAND (exp, 1));
> - return MIN (c0, c1);
> -
> - case MULT_EXPR:
> - c0 = highest_pow2_factor (TREE_OPERAND (exp, 0));
> - c1 = highest_pow2_factor (TREE_OPERAND (exp, 1));
> - return c0 * c1;
> -
> - case ROUND_DIV_EXPR: case TRUNC_DIV_EXPR: case FLOOR_DIV_EXPR:
> - case CEIL_DIV_EXPR:
> - if (integer_pow2p (TREE_OPERAND (exp, 1))
> - && host_integerp (TREE_OPERAND (exp, 1), 1))
> - {
> - c0 = highest_pow2_factor (TREE_OPERAND (exp, 0));
> - c1 = tree_low_cst (TREE_OPERAND (exp, 1), 1);
> - return MAX (1, c0 / c1);
> - }
> - break;
> -
> - case BIT_AND_EXPR:
> - /* The highest power of two of a bit-and expression is the maximum of
> - that of its operands. We typically get here for a complex LHS and
> - a constant negative power of two on the RHS to force an explicit
> - alignment, so don't bother looking at the LHS. */
> - return highest_pow2_factor (TREE_OPERAND (exp, 1));
> -
> - CASE_CONVERT:
> - case SAVE_EXPR:
> - return highest_pow2_factor (TREE_OPERAND (exp, 0));
> -
> - case COMPOUND_EXPR:
> - return highest_pow2_factor (TREE_OPERAND (exp, 1));
> -
> - case COND_EXPR:
> - c0 = highest_pow2_factor (TREE_OPERAND (exp, 1));
> - c1 = highest_pow2_factor (TREE_OPERAND (exp, 2));
> - return MIN (c0, c1);
> -
> - default:
> - break;
> - }
> -
> - return 1;
> + unsigned HOST_WIDE_INT ret;
> + int trailing_zeros = tree_ctz (exp);
> + if (trailing_zeros >= HOST_BITS_PER_WIDE_INT)
> + return BIGGEST_ALIGNMENT;
> + ret = (unsigned HOST_WIDE_INT) 1 << trailing_zeros;
> + if (ret > BIGGEST_ALIGNMENT)
> + return BIGGEST_ALIGNMENT;
> + return ret;
> }
>
> /* Similar, except that the alignment requirements of TARGET are
> --- gcc/tree-vect-loop.c.jj 2013-10-24 10:19:23.000000000 +0200
> +++ gcc/tree-vect-loop.c 2013-10-25 14:01:35.968407222 +0200
> @@ -1586,9 +1586,9 @@ vect_analyze_loop_operations (loop_vec_i
> return false;
> }
>
> - if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
> - || LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0
> - || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
> + if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo)
> + || (tree_ctz (LOOP_VINFO_NITERS (loop_vinfo))
> + < exact_log2 (vectorization_factor)))
> {
> if (dump_enabled_p ())
> dump_printf_loc (MSG_NOTE, vect_location, "epilog loop required.\n");
> @@ -5656,15 +5656,20 @@ vect_transform_loop (loop_vec_info loop_
> will remain scalar and will compute the remaining (n%VF) iterations.
> (VF is the vectorization factor). */
>
> - if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
> - || (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
> - && LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0)
> - || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo))
> + if (tree_ctz (LOOP_VINFO_NITERS (loop_vinfo))
> + < exact_log2 (vectorization_factor)
> + || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo))
> vect_do_peeling_for_loop_bound (loop_vinfo, &ratio,
> th, check_profitability);
> - else
> + else if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
> ratio = build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo)),
> LOOP_VINFO_INT_NITERS (loop_vinfo) / vectorization_factor);
> + else
> + {
> + tree ni_name, ratio_mult_vf;
> + vect_generate_tmps_on_preheader (loop_vinfo, &ni_name, &ratio_mult_vf,
> + &ratio, NULL);
> + }
>
> /* 1) Make sure the loop header has exactly two entries
> 2) Make sure we have a preheader basic block. */
> --- gcc/builtins.c.jj 2013-10-23 14:43:12.000000000 +0200
> +++ gcc/builtins.c 2013-10-25 12:31:49.426022284 +0200
> @@ -309,7 +309,7 @@ get_object_alignment_2 (tree exp, unsign
> tree offset;
> enum machine_mode mode;
> int unsignedp, volatilep;
> - unsigned int inner, align = BITS_PER_UNIT;
> + unsigned int align = BITS_PER_UNIT;
> bool known_alignment = false;
>
> /* Get the innermost object and the constant (bitpos) and possibly
> @@ -418,50 +418,16 @@ get_object_alignment_2 (tree exp, unsign
>
> /* If there is a non-constant offset part extract the maximum
> alignment that can prevail. */
> - inner = ~0U;
> - while (offset)
> + if (offset)
> {
> - tree next_offset;
> -
> - if (TREE_CODE (offset) == PLUS_EXPR)
> - {
> - next_offset = TREE_OPERAND (offset, 0);
> - offset = TREE_OPERAND (offset, 1);
> - }
> - else
> - next_offset = NULL;
> - if (host_integerp (offset, 1))
> - {
> - /* Any overflow in calculating offset_bits won't change
> - the alignment. */
> - unsigned offset_bits
> - = ((unsigned) tree_low_cst (offset, 1) * BITS_PER_UNIT);
> -
> - if (offset_bits)
> - inner = MIN (inner, (offset_bits & -offset_bits));
> - }
> - else if (TREE_CODE (offset) == MULT_EXPR
> - && host_integerp (TREE_OPERAND (offset, 1), 1))
> - {
> - /* Any overflow in calculating offset_factor won't change
> - the alignment. */
> - unsigned offset_factor
> - = ((unsigned) tree_low_cst (TREE_OPERAND (offset, 1), 1)
> - * BITS_PER_UNIT);
> -
> - if (offset_factor)
> - inner = MIN (inner, (offset_factor & -offset_factor));
> - }
> - else
> + int trailing_zeros = tree_ctz (offset);
> + if (trailing_zeros < HOST_BITS_PER_INT)
> {
> - inner = MIN (inner, BITS_PER_UNIT);
> - break;
> + unsigned int inner = (1U << trailing_zeros) * BITS_PER_UNIT;
> + if (inner)
> + align = MIN (align, inner);
> }
> - offset = next_offset;
> }
> - /* Alignment is innermost object alignment adjusted by the constant
> - and non-constant offset parts. */
> - align = MIN (align, inner);
>
> *alignp = align;
> *bitposp = bitpos & (*alignp - 1);
>
>
> Jakub
>
>
--
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend
More information about the Gcc-patches
mailing list