On Tue, 12 Nov 2013, Cong Hou wrote:
> The current alias check merger does not consider the DR_STEP of
> data-refs when sorting data-refs. For the following loop:
>
> for (i = 0; i < N; ++i)
> a[i] = b[0] + b[i] + b[1];
>
> The data ref b[0] and b[i] have the same DR_INIT and DR_OFFSET, and
> after sorting three DR pairs, the following order can be a possible
> result:
>
> (a[i], b[0]), (a[i], b[i]), (a[i], b[1])
>
> This prevents the alias checks for (a[i], b[0]) and (a[i], b[1]) being
> merged.
>
> This patch added the comparison between DR_STEP of two data refs
> during the sort.
>
> The test case is also updated. The previous one used explicit
> dg-options which blocks the options from the target vect_int. The test
> case also assumes a vector can hold at least 4 integers of int type,
> which may not be true on some targets.
>
> The patch is pasted below. Bootstrapped and tested on a x86-64 machine.
Ok.
Thanks,
Richard.
>
>
> thanks,
> Cong
>
>
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 2c0554b..5faa5ca 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,14 @@
> +2013-11-12 Cong Hou <co...@google.com>
> +
> + * tree-vectorizer.h (struct dr_with_seg_len): Remove the base
> + address field as it can be obtained from dr. Rename the struct.
> + * tree-vect-data-refs.c (comp_dr_with_seg_len_pair): Consider
> + steps of data references during sort.
> + (vect_prune_runtime_alias_test_list): Adjust with the change to
> + struct dr_with_seg_len.
> + * tree-vect-loop-manip.c (vect_create_cond_for_alias_checks):
> + Adjust with the change to struct dr_with_seg_len.
> +
> 2013-11-12 Jeff Law <l...@redhat.com>
>
> * tree-ssa-threadedge.c (thread_around_empty_blocks): New
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index 09c7f20..8075409 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,7 @@
> +2013-11-12 Cong Hou <co...@google.com>
> +
> + * gcc.dg/vect/vect-alias-check.c: Update.
> +
> 2013-11-12 Balaji V. Iyer <balaji.v.i...@intel.com>
>
> * gcc.dg/cilk-plus/cilk-plus.exp: Added a check for LTO before running
> diff --git a/gcc/testsuite/gcc.dg/vect/vect-alias-check.c
> b/gcc/testsuite/gcc.dg/vect/vect-alias-check.c
> index 64a4e0c..c1bffed 100644
> --- a/gcc/testsuite/gcc.dg/vect/vect-alias-check.c
> +++ b/gcc/testsuite/gcc.dg/vect/vect-alias-check.c
> @@ -1,17 +1,17 @@
> /* { dg-require-effective-target vect_int } */
> /* { dg-do compile } */
> -/* { dg-options "-O2 -ftree-vectorize
> --param=vect-max-version-for-alias-checks=2 -fdump-tree-vect-details"
> } */
> +/* { dg-additional-options "--param=vect-max-version-for-alias-checks=2" } */
>
> -/* A test case showing three potential alias checks between
> - a[i] and b[i], b[i+7], b[i+14]. With alias checks merging
> - enabled, those tree checks can be merged into one, and the
> - loop will be vectorized with vect-max-version-for-alias-checks=2. */
> +/* A test case showing four potential alias checks between a[i] and b[0],
> b[1],
> + b[i+1] and b[i+2]. With alias check merging enabled, those four checks
> + can be merged into two, and the loop will be vectorized with
> + vect-max-version-for-alias-checks=2. */
>
> void foo (int *a, int *b)
> {
> int i;
> for (i = 0; i < 1000; ++i)
> - a[i] = b[i] + b[i+7] + b[i+14];
> + a[i] = b[0] + b[1] + b[i+1] + b[i+2];
> }
>
> /* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
> diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c
> index c479775..7f0920d 100644
> --- a/gcc/tree-vect-data-refs.c
> +++ b/gcc/tree-vect-data-refs.c
> @@ -2620,7 +2620,7 @@ vect_analyze_data_ref_accesses (loop_vec_info
> loop_vinfo, bb_vec_info bb_vinfo)
> }
>
>
> -/* Operator == between two dr_addr_with_seg_len objects.
> +/* Operator == between two dr_with_seg_len objects.
>
> This equality operator is used to make sure two data refs
> are the same one so that we will consider to combine the
> @@ -2628,62 +2628,51 @@ vect_analyze_data_ref_accesses (loop_vec_info
> loop_vinfo, bb_vec_info bb_vinfo)
> refs. */
>
> static bool
> -operator == (const dr_addr_with_seg_len& d1,
> - const dr_addr_with_seg_len& d2)
> +operator == (const dr_with_seg_len& d1,
> + const dr_with_seg_len& d2)
> {
> - return operand_equal_p (d1.basic_addr, d2.basic_addr, 0)
> - && compare_tree (d1.offset, d2.offset) == 0
> - && compare_tree (d1.seg_len, d2.seg_len) == 0;
> + return operand_equal_p (DR_BASE_ADDRESS (d1.dr),
> + DR_BASE_ADDRESS (d2.dr), 0)
> + && compare_tree (d1.offset, d2.offset) == 0
> + && compare_tree (d1.seg_len, d2.seg_len) == 0;
> }
>
> -/* Function comp_dr_addr_with_seg_len_pair.
> +/* Function comp_dr_with_seg_len_pair.
>
> - Comparison function for sorting objects of dr_addr_with_seg_len_pair_t
> + Comparison function for sorting objects of dr_with_seg_len_pair_t
> so that we can combine aliasing checks in one scan. */
>
> static int
> -comp_dr_addr_with_seg_len_pair (const void *p1_, const void *p2_)
> +comp_dr_with_seg_len_pair (const void *p1_, const void *p2_)
> {
> - const dr_addr_with_seg_len_pair_t* p1 =
> - (const dr_addr_with_seg_len_pair_t *) p1_;
> - const dr_addr_with_seg_len_pair_t* p2 =
> - (const dr_addr_with_seg_len_pair_t *) p2_;
> -
> - const dr_addr_with_seg_len &p11 = p1->first,
> - &p12 = p1->second,
> - &p21 = p2->first,
> - &p22 = p2->second;
> -
> - int comp_res = compare_tree (p11.basic_addr, p21.basic_addr);
> - if (comp_res != 0)
> + const dr_with_seg_len_pair_t* p1 = (const dr_with_seg_len_pair_t *) p1_;
> + const dr_with_seg_len_pair_t* p2 = (const dr_with_seg_len_pair_t *) p2_;
> +
> + const dr_with_seg_len &p11 = p1->first,
> + &p12 = p1->second,
> + &p21 = p2->first,
> + &p22 = p2->second;
> +
> + /* For DR pairs (a, b) and (c, d), we only consider to merge the alias
> checks
> + if a and c have the same basic address snd step, and b and d have the
> same
> + address and step. Therefore, if any a&c or b&d don't have the
> same address
> + and step, we don't care the order of those two pairs after sorting. */
> + int comp_res;
> +
> + if ((comp_res = compare_tree (DR_BASE_ADDRESS (p11.dr),
> + DR_BASE_ADDRESS (p21.dr))) != 0)
> return comp_res;
> -
> - comp_res = compare_tree (p12.basic_addr, p22.basic_addr);
> - if (comp_res != 0)
> + if ((comp_res = compare_tree (DR_BASE_ADDRESS (p12.dr),
> + DR_BASE_ADDRESS (p22.dr))) != 0)
> + return comp_res;
> + if ((comp_res = compare_tree (DR_STEP (p11.dr), DR_STEP (p21.dr))) != 0)
> + return comp_res;
> + if ((comp_res = compare_tree (DR_STEP (p12.dr), DR_STEP (p22.dr))) != 0)
> + return comp_res;
> + if ((comp_res = compare_tree (p11.offset, p21.offset)) != 0)
> + return comp_res;
> + if ((comp_res = compare_tree (p12.offset, p22.offset)) != 0)
> return comp_res;
> -
> - if (TREE_CODE (p11.offset) != INTEGER_CST
> - || TREE_CODE (p21.offset) != INTEGER_CST)
> - {
> - comp_res = compare_tree (p11.offset, p21.offset);
> - if (comp_res != 0)
> - return comp_res;
> - }
> - else if (tree_int_cst_compare (p11.offset, p21.offset) < 0)
> - return -1;
> - else if (tree_int_cst_compare (p11.offset, p21.offset) > 0)
> - return 1;
> - if (TREE_CODE (p12.offset) != INTEGER_CST
> - || TREE_CODE (p22.offset) != INTEGER_CST)
> - {
> - comp_res = compare_tree (p12.offset, p22.offset);
> - if (comp_res != 0)
> - return comp_res;
> - }
> - else if (tree_int_cst_compare (p12.offset, p22.offset) < 0)
> - return -1;
> - else if (tree_int_cst_compare (p12.offset, p22.offset) > 0)
> - return 1;
>
> return 0;
> }
> @@ -2718,11 +2707,11 @@ vect_vfa_segment_size (struct data_reference
> *dr, tree length_factor)
> segment_length = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)));
> else
> segment_length = size_binop (MULT_EXPR,
> - fold_convert (sizetype, DR_STEP (dr)),
> - fold_convert (sizetype, length_factor));
> + fold_convert (sizetype, DR_STEP (dr)),
> + fold_convert (sizetype, length_factor));
>
> if (vect_supportable_dr_alignment (dr, false)
> - == dr_explicit_realign_optimized)
> + == dr_explicit_realign_optimized)
> {
> tree vector_size = TYPE_SIZE_UNIT
> (STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr))));
> @@ -2744,7 +2733,7 @@ vect_prune_runtime_alias_test_list
> (loop_vec_info loop_vinfo)
> {
> vec<ddr_p> may_alias_ddrs =
> LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo);
> - vec<dr_addr_with_seg_len_pair_t>& comp_alias_ddrs =
> + vec<dr_with_seg_len_pair_t>& comp_alias_ddrs =
> LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo);
> int vect_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
> tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo);
> @@ -2823,18 +2812,11 @@ vect_prune_runtime_alias_test_list
> (loop_vec_info loop_vinfo)
> segment_length_a = vect_vfa_segment_size (dr_a, length_factor);
> segment_length_b = vect_vfa_segment_size (dr_b, length_factor);
>
> - dr_addr_with_seg_len_pair_t dr_with_seg_len_pair
> - (dr_addr_with_seg_len
> - (dr_a, DR_BASE_ADDRESS (dr_a),
> - size_binop (PLUS_EXPR, DR_OFFSET (dr_a), DR_INIT (dr_a)),
> - segment_length_a),
> - dr_addr_with_seg_len
> - (dr_b, DR_BASE_ADDRESS (dr_b),
> - size_binop (PLUS_EXPR, DR_OFFSET (dr_b), DR_INIT (dr_b)),
> - segment_length_b));
> -
> - if (compare_tree (dr_with_seg_len_pair.first.basic_addr,
> - dr_with_seg_len_pair.second.basic_addr) > 0)
> + dr_with_seg_len_pair_t dr_with_seg_len_pair
> + (dr_with_seg_len (dr_a, segment_length_a),
> + dr_with_seg_len (dr_b, segment_length_b));
> +
> + if (compare_tree (DR_BASE_ADDRESS (dr_a), DR_BASE_ADDRESS (dr_b)) > 0)
> swap (dr_with_seg_len_pair.first, dr_with_seg_len_pair.second);
>
> comp_alias_ddrs.safe_push (dr_with_seg_len_pair);
> @@ -2842,17 +2824,17 @@ vect_prune_runtime_alias_test_list
> (loop_vec_info loop_vinfo)
>
> /* Second, we sort the collected data ref pairs so that we can scan
> them once to combine all possible aliasing checks. */
> - comp_alias_ddrs.qsort (comp_dr_addr_with_seg_len_pair);
> + comp_alias_ddrs.qsort (comp_dr_with_seg_len_pair);
>
> /* Third, we scan the sorted dr pairs and check if we can combine
> alias checks of two neighbouring dr pairs. */
> for (size_t i = 1; i < comp_alias_ddrs.length (); ++i)
> {
> /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2). */
> - dr_addr_with_seg_len *dr_a1 = &comp_alias_ddrs[i-1].first,
> - *dr_b1 = &comp_alias_ddrs[i-1].second,
> - *dr_a2 = &comp_alias_ddrs[i].first,
> - *dr_b2 = &comp_alias_ddrs[i].second;
> + dr_with_seg_len *dr_a1 = &comp_alias_ddrs[i-1].first,
> + *dr_b1 = &comp_alias_ddrs[i-1].second,
> + *dr_a2 = &comp_alias_ddrs[i].first,
> + *dr_b2 = &comp_alias_ddrs[i].second;
>
> /* Remove duplicate data ref pairs. */
> if (*dr_a1 == *dr_a2 && *dr_b1 == *dr_b2)
> @@ -2889,7 +2871,9 @@ vect_prune_runtime_alias_test_list
> (loop_vec_info loop_vinfo)
> swap (dr_a2, dr_b2);
> }
>
> - if (!operand_equal_p (dr_a1->basic_addr, dr_a2->basic_addr, 0)
> + if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1->dr),
> + DR_BASE_ADDRESS (dr_a2->dr),
> + 0)
> || !host_integerp (dr_a1->offset, 0)
> || !host_integerp (dr_a2->offset, 0))
> continue;
> @@ -2916,8 +2900,8 @@ vect_prune_runtime_alias_test_list
> (loop_vec_info loop_vinfo)
>
> HOST_WIDE_INT
> min_seg_len_b = (TREE_CODE (dr_b1->seg_len) == INTEGER_CST) ?
> - TREE_INT_CST_LOW (dr_b1->seg_len) :
> - vect_factor;
> + TREE_INT_CST_LOW (dr_b1->seg_len) :
> + vect_factor;
>
> if (diff <= min_seg_len_b
> || (TREE_CODE (dr_a1->seg_len) == INTEGER_CST
> diff --git a/gcc/tree-vect-loop-manip.c b/gcc/tree-vect-loop-manip.c
> index 15227856..b8e56c4 100644
> --- a/gcc/tree-vect-loop-manip.c
> +++ b/gcc/tree-vect-loop-manip.c
> @@ -2242,7 +2242,7 @@ vect_create_cond_for_align_checks (loop_vec_info
> loop_vinfo,
> void
> vect_create_cond_for_alias_checks (loop_vec_info loop_vinfo, tree *
> cond_expr)
> {
> - vec<dr_addr_with_seg_len_pair_t> comp_alias_ddrs =
> + vec<dr_with_seg_len_pair_t> comp_alias_ddrs =
> LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo);
> tree part_cond_expr;
>
> @@ -2260,15 +2260,15 @@ vect_create_cond_for_alias_checks
> (loop_vec_info loop_vinfo, tree * cond_expr)
>
> for (size_t i = 0, s = comp_alias_ddrs.length (); i < s; ++i)
> {
> - const dr_addr_with_seg_len& dr_a = comp_alias_ddrs[i].first;
> - const dr_addr_with_seg_len& dr_b = comp_alias_ddrs[i].second;
> + const dr_with_seg_len& dr_a = comp_alias_ddrs[i].first;
> + const dr_with_seg_len& dr_b = comp_alias_ddrs[i].second;
> tree segment_length_a = dr_a.seg_len;
> tree segment_length_b = dr_b.seg_len;
>
> tree addr_base_a
> - = fold_build_pointer_plus (dr_a.basic_addr, dr_a.offset);
> + = fold_build_pointer_plus (DR_BASE_ADDRESS (dr_a.dr), dr_a.offset);
> tree addr_base_b
> - = fold_build_pointer_plus (dr_b.basic_addr, dr_b.offset);
> + = fold_build_pointer_plus (DR_BASE_ADDRESS (dr_b.dr), dr_b.offset);
>
> if (dump_enabled_p ())
> {
> diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
> index bbd50e1..0ce78d9 100644
> --- a/gcc/tree-vectorizer.h
> +++ b/gcc/tree-vectorizer.h
> @@ -176,32 +176,33 @@ typedef struct _slp_oprnd_info
>
>
> /* This struct is used to store the information of a data reference,
> - including the data ref itself, its basic address, the access offset
> - and the segment length for aliasing checks. This is used to generate
> - alias checks. */
> + including the data ref itself, the access offset (calculated by summing
> its
> + offset and init) and the segment length for aliasing checks.
> + This is used to merge alias checks. */
>
> -struct dr_addr_with_seg_len
> +struct dr_with_seg_len
> {
> - dr_addr_with_seg_len (data_reference* d, tree addr, tree off, tree len)
> - : dr (d), basic_addr (addr), offset (off), seg_len (len) {}
> + dr_with_seg_len (data_reference_p d, tree len)
> + : dr (d),
> + offset (size_binop (PLUS_EXPR, DR_OFFSET (d), DR_INIT (d))),
> + seg_len (len) {}
>
> - data_reference *dr;
> - tree basic_addr;
> + data_reference_p dr;
> tree offset;
> tree seg_len;
> };
>
> -/* This struct contains two dr_addr_with_seg_len objects with aliasing data
> +/* This struct contains two dr_with_seg_len objects with aliasing data
> refs. Two comparisons are generated from them. */
>
> -struct dr_addr_with_seg_len_pair_t
> +struct dr_with_seg_len_pair_t
> {
> - dr_addr_with_seg_len_pair_t (const dr_addr_with_seg_len& d1,
> - const dr_addr_with_seg_len& d2)
> + dr_with_seg_len_pair_t (const dr_with_seg_len& d1,
> + const dr_with_seg_len& d2)
> : first (d1), second (d2) {}
>
> - dr_addr_with_seg_len first;
> - dr_addr_with_seg_len second;
> + dr_with_seg_len first;
> + dr_with_seg_len second;
> };
>
>
> @@ -306,7 +307,7 @@ typedef struct _loop_vec_info {
>
> /* Data Dependence Relations defining address ranges together with segment
> lengths from which the run-time aliasing check is built. */
> - vec<dr_addr_with_seg_len_pair_t> comp_alias_ddrs;
> + vec<dr_with_seg_len_pair_t> comp_alias_ddrs;
>
> /* Statements in the loop that have data references that are candidates
> for a
> runtime (loop versioning) misalignment check. */
>
