Hi,
GCC now generates duplicated alias check in vectorizer when versioning loops.
In current implementation, DR_OFFSET and DR_INIT are added together too early
when creating structure dr_with_seg_len. This has two disadvantages: A)
structure dr_with_seg_len_pair_t is only canonicalized against DR_BASE_ADDRESS
in function vect_prune_runtime_alias_test_list, while it should be against
DR_OFFSET too; B) When function vect_prune_runtime_alias_test_list tries to
merge aias checks with consecutive memory references, it can only handle DRs
with constant DR_OFFSET + DR_INIT, as in below code:
/* We consider the case that DR_B1 and DR_B2 are same memrefs,
and DR_A1 and DR_A2 are two consecutive memrefs. */
//... ...
if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1->dr),
DR_BASE_ADDRESS (dr_a2->dr),
0)
|| !tree_fits_shwi_p (dr_a1->offset)
|| !tree_fits_shwi_p (dr_a2->offset))
continue;
Both disadvantages result in duplicated/unnecessary alias checks, as well as
bloated condition basic block of loop versioning.
This patch fixes the issue. Bootstrap and test on x86_64 and AArch64. Is it
OK?
Test gfortran.dg/vect/vect-8.f90 failed now. It scans for "vectorized 20
loops" but with this patch there are more than 20 loops vectorized. The
additional loop wasn't vectorized because # of alias checks exceeded parameter
bound "vect-max-version-for-alias-checks" w/o this patch.
There are other issues in vectorizer alias checking, I will tackle them in
follow up patches.
Thanks,
bin
2016-06-03 Bin Cheng <bin.ch...@arm.com>
* tree-vectorizer.h (struct dr_with_seg_len): Remove class
member OFFSET.
* tree-vect-data-refs.c (operator ==): Handle DR_OFFSET directly,
rather than OFFSET.
(comp_dr_with_seg_len_pair, comp_dr_with_seg_len_pair): Ditto.
(vect_create_cond_for_alias_checks): Ditto.
(vect_prune_runtime_alias_test_list): Also canonicalize pairs
against DR_OFFSET. Handle DR_OFFSET directly when prune alias
checks.
gcc/testsuite/ChangeLog
2016-06-03 Bin Cheng <bin.ch...@arm.com>
* gcc.dg/vect/vect-alias-check-1.c: New test.
diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c
index 36d302a..ba4d637 100644
--- a/gcc/tree-vect-data-refs.c
+++ b/gcc/tree-vect-data-refs.c
@@ -2845,7 +2845,8 @@ operator == (const dr_with_seg_len& d1,
{
return operand_equal_p (DR_BASE_ADDRESS (d1.dr),
DR_BASE_ADDRESS (d2.dr), 0)
- && compare_tree (d1.offset, d2.offset) == 0
+ && compare_tree (DR_OFFSET (d1.dr), DR_OFFSET (d2.dr)) == 0
+ && compare_tree (DR_INIT (d1.dr), DR_INIT (d2.dr)) == 0
&& compare_tree (d1.seg_len, d2.seg_len) == 0;
}
@@ -2855,15 +2856,12 @@ operator == (const dr_with_seg_len& d1,
so that we can combine aliasing checks in one scan. */
static int
-comp_dr_with_seg_len_pair (const void *p1_, const void *p2_)
+comp_dr_with_seg_len_pair (const void *pa_, const void *pb_)
{
- 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;
+ const dr_with_seg_len_pair_t* pa = (const dr_with_seg_len_pair_t *) pa_;
+ const dr_with_seg_len_pair_t* pb = (const dr_with_seg_len_pair_t *) pb_;
+ const dr_with_seg_len &a1 = pa->first, &a2 = pa->second;
+ const dr_with_seg_len &b1 = pb->first, &b2 = pb->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
@@ -2871,19 +2869,23 @@ comp_dr_with_seg_len_pair (const void *p1_, const void
*p2_)
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)
+ if ((comp_res = compare_tree (DR_BASE_ADDRESS (a1.dr),
+ DR_BASE_ADDRESS (b1.dr))) != 0)
+ return comp_res;
+ if ((comp_res = compare_tree (DR_BASE_ADDRESS (a2.dr),
+ DR_BASE_ADDRESS (b2.dr))) != 0)
return comp_res;
- if ((comp_res = compare_tree (DR_BASE_ADDRESS (p12.dr),
- DR_BASE_ADDRESS (p22.dr))) != 0)
+ if ((comp_res = compare_tree (DR_STEP (a1.dr), DR_STEP (b1.dr))) != 0)
return comp_res;
- if ((comp_res = compare_tree (DR_STEP (p11.dr), DR_STEP (p21.dr))) != 0)
+ if ((comp_res = compare_tree (DR_STEP (a2.dr), DR_STEP (b2.dr))) != 0)
return comp_res;
- if ((comp_res = compare_tree (DR_STEP (p12.dr), DR_STEP (p22.dr))) != 0)
+ if ((comp_res = compare_tree (DR_OFFSET (a1.dr), DR_OFFSET (b1.dr))) != 0)
return comp_res;
- if ((comp_res = compare_tree (p11.offset, p21.offset)) != 0)
+ if ((comp_res = compare_tree (DR_INIT (a1.dr), DR_INIT (b1.dr))) != 0)
return comp_res;
- if ((comp_res = compare_tree (p12.offset, p22.offset)) != 0)
+ if ((comp_res = compare_tree (DR_OFFSET (a2.dr), DR_OFFSET (b2.dr))) != 0)
+ return comp_res;
+ if ((comp_res = compare_tree (DR_INIT (a2.dr), DR_INIT (b2.dr))) != 0)
return comp_res;
return 0;
@@ -2986,6 +2988,7 @@ vect_prune_runtime_alias_test_list (loop_vec_info
loop_vinfo)
/* First, we collect all data ref pairs for aliasing checks. */
FOR_EACH_VEC_ELT (may_alias_ddrs, i, ddr)
{
+ int comp_res;
struct data_reference *dr_a, *dr_b;
gimple *dr_group_first_a, *dr_group_first_b;
tree segment_length_a, segment_length_b;
@@ -3020,7 +3023,11 @@ vect_prune_runtime_alias_test_list (loop_vec_info
loop_vinfo)
(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)
+ /* Canonicalize pairs by sorting the two DR members. */
+ comp_res = compare_tree (DR_BASE_ADDRESS (dr_a), DR_BASE_ADDRESS (dr_b));
+ if (comp_res > 0
+ || (comp_res == 0
+ && compare_tree (DR_OFFSET (dr_a), DR_OFFSET (dr_b)) > 0))
std::swap (dr_with_seg_len_pair.first, dr_with_seg_len_pair.second);
comp_alias_ddrs.safe_push (dr_with_seg_len_pair);
@@ -3076,21 +3083,21 @@ vect_prune_runtime_alias_test_list (loop_vec_info
loop_vinfo)
}
if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1->dr),
- DR_BASE_ADDRESS (dr_a2->dr),
- 0)
- || !tree_fits_shwi_p (dr_a1->offset)
- || !tree_fits_shwi_p (dr_a2->offset))
+ DR_BASE_ADDRESS (dr_a2->dr), 0)
+ || !operand_equal_p (DR_OFFSET (dr_a1->dr),
+ DR_OFFSET (dr_a2->dr), 0)
+ || !tree_fits_shwi_p (DR_INIT (dr_a1->dr))
+ || !tree_fits_shwi_p (DR_INIT (dr_a2->dr)))
continue;
/* Make sure dr_a1 starts left of dr_a2. */
- if (tree_int_cst_lt (dr_a2->offset, dr_a1->offset))
+ if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr)))
std::swap (*dr_a1, *dr_a2);
- unsigned HOST_WIDE_INT diff
- = tree_to_shwi (dr_a2->offset) - tree_to_shwi (dr_a1->offset);
-
-
bool do_remove = false;
+ unsigned HOST_WIDE_INT diff
+ = (tree_to_shwi (DR_INIT (dr_a2->dr))
+ - tree_to_shwi (DR_INIT (dr_a1->dr)));
/* If the left segment does not extend beyond the start of the
right segment the new segment length is that of the right
@@ -3118,7 +3125,7 @@ vect_prune_runtime_alias_test_list (loop_vec_info
loop_vinfo)
DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
- where DIFF = DR_A2->OFFSET - DR_A1->OFFSET. However,
+ where DIFF = DR_A2_INIT - DR_A1_INIT. However,
SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
have to make a best estimation. We can get the minimum value
of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
diff --git a/gcc/tree-vect-loop-manip.c b/gcc/tree-vect-loop-manip.c
index 7ec6dae..438458e 100644
--- a/gcc/tree-vect-loop-manip.c
+++ b/gcc/tree-vect-loop-manip.c
@@ -2241,11 +2241,16 @@ vect_create_cond_for_alias_checks (loop_vec_info
loop_vinfo, tree * cond_expr)
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_BASE_ADDRESS (dr_a.dr), dr_a.offset);
- tree addr_base_b
- = fold_build_pointer_plus (DR_BASE_ADDRESS (dr_b.dr), dr_b.offset);
+ tree addr_base_a = DR_BASE_ADDRESS (dr_a.dr);
+ tree addr_base_b = DR_BASE_ADDRESS (dr_b.dr);
+ tree offset_a = DR_OFFSET (dr_a.dr), offset_b = DR_OFFSET (dr_b.dr);
+
+ offset_a = fold_build2 (PLUS_EXPR, TREE_TYPE (offset_a),
+ offset_a, DR_INIT (dr_a.dr));
+ offset_b = fold_build2 (PLUS_EXPR, TREE_TYPE (offset_b),
+ offset_b, DR_INIT (dr_b.dr));
+ addr_base_a = fold_build_pointer_plus (addr_base_a, offset_a);
+ addr_base_b = fold_build_pointer_plus (addr_base_b, offset_b);
if (dump_enabled_p ())
{
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 5816006..1b46b65 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -146,19 +146,15 @@ typedef struct _slp_instance {
/* This struct is used to store the information of a data reference,
- 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. */
+ including the data ref itself and the segment length for aliasing
+ checks. This is used to merge alias checks. */
struct dr_with_seg_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) {}
+ : dr (d), seg_len (len) {}
data_reference_p dr;
- tree offset;
tree seg_len;
};
diff --git a/gcc/testsuite/gcc.dg/vect/vect-alias-check-1.c
b/gcc/testsuite/gcc.dg/vect/vect-alias-check-1.c
new file mode 100644
index 0000000..955084c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-alias-check-1.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-additional-options "-Ofast" } */
+
+int b, c = 1;
+int a[6][5] = { {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 1, 0, 0, 0} };
+
+void
+fn1 ()
+{
+ int d;
+ for (b = 0; b < 5; b++)
+ for (d = 4; d; d--)
+ a[c + 1][b] = a[d + 1][d];
+}
+
+/* { dg-final { scan-tree-dump "improved number of alias checks from \[0-9\]*
to 1" "vect" } } */