Hi,
This patch fixes PR80815 in which negative DR_STEP is mis-handled. It does
below:
1) Reorder three cases in which we merge alias checks, in order like:
old_case_A -> new_case_B
old_case_B -> new_case_C (and removed as described in 3))
old_case_C -> new_case_A
This is because new_case_1 is accurate check that doesn't introduce false
alias,
while the other two does.
2) Explicitly comment that Case A and B combined together can merge all
dr_a1&dr_b and
dr_a2&dr_b pairs if SEGMENT_LEN_A is constant. We still keep Case A/B
separately
for clarity, also because Case A doesn't introduces false alias, while B
does.
3) Remove the old_case_C:
/* Generally the new segment length is the maximum of the
left segment size and the right segment size plus the distance.
??? We can also build tree MAX_EXPR here but it's not clear this
is profitable. */
else if (tree_fits_uhwi_p (dr_a1->seg_len)
&& tree_fits_uhwi_p (dr_a2->seg_len))
This check is actually covered by A and B.
4) Handle negative DR_STEPs explicitly.
5) Add two tests illustrating wrong alias checking issue.
Bootstrap and test on x86_64 and AArch64, is it OK?
BTW, I tried to keep the change as minimal as possible, but ended up with quite
amount refactoring because the old cases are somehow duplicated/complicated,
and not fit to negative DR_STEPs handling.
Thanks,
bin
2017-05-22 Bin Cheng <bin.ch...@arm.com>
PR tree-optimization/80815
* tree-data-ref.c (prune_runtime_alias_test_list): Simplify condition
for merging runtime alias checks. Handle negative DR_STEPs.
gcc/testsuite/ChangeLog
2017-05-22 Bin Cheng <bin.ch...@arm.com>
PR tree-optimization/80815
* gcc.dg/vect/pr80815-1.c: New test.
* gcc.dg/vect/pr80815-2.c: New test.From af1dda073f8bd1a371cd1207fcaf467be0dc1106 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binch...@e108451-lin.cambridge.arm.com>
Date: Fri, 19 May 2017 18:46:14 +0100
Subject: [PATCH 3/6] negative-step-alias-check-20170516.txt
---
gcc/testsuite/gcc.dg/vect/pr80815-1.c | 38 ++++++++++
gcc/testsuite/gcc.dg/vect/pr80815-2.c | 46 ++++++++++++
gcc/tree-data-ref.c | 131 +++++++++++++++++++++++-----------
3 files changed, 175 insertions(+), 40 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/vect/pr80815-1.c
create mode 100644 gcc/testsuite/gcc.dg/vect/pr80815-2.c
diff --git a/gcc/testsuite/gcc.dg/vect/pr80815-1.c
b/gcc/testsuite/gcc.dg/vect/pr80815-1.c
new file mode 100644
index 0000000..98c06c0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/pr80815-1.c
@@ -0,0 +1,38 @@
+/* { dg-require-effective-target vect_int } */
+
+#include "tree-vect.h"
+int arr[2048];
+
+__attribute__ ((noinline)) int
+foo (int *a, int *b)
+{
+ int i;
+ int *a1 = a;
+ int *a0 = a1 - 512;
+ for (i = 0; i < 500; i++)
+ {
+ *b = *a0 + *a1;
+ b++;
+ a0--;
+ a1--;
+ }
+ return 0;
+}
+
+int main (void)
+{
+ int *a = &arr[1027];
+ int *b = &arr[1024];
+
+ int i;
+ for (i = 0; i < 2048; i++)
+ arr[i] = i;
+
+ foo (a, b);
+
+ if (arr[1026] != 2053 || arr[1027] != 2054)
+ abort ();
+
+ return 0;
+}
+
diff --git a/gcc/testsuite/gcc.dg/vect/pr80815-2.c
b/gcc/testsuite/gcc.dg/vect/pr80815-2.c
new file mode 100644
index 0000000..83557da
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/pr80815-2.c
@@ -0,0 +1,46 @@
+/* { dg-require-effective-target vect_int } */
+
+#include "tree-vect.h"
+int arr[2048];
+int res[100] = { 13198, 13224, 12735, 12760, 12270, 12294,
+ 11803, 11826, 11334, 11356, 10863, 10884,
+ 10390, 10410, 9915, 9934, 9438, 9456,
+ 8959, 8976, 8478, 8494, 7995, 8010,
+ 7510, 7524, 7023, 7036, 6534, 6546,
+ 6043, 6054, 5550, 5560, 5055, 5064,
+ 4558, 4566, 4059, 4066, 3558, 3564,
+ 3055, 3060, 2550, 2554, 2043, 0};
+
+__attribute__ ((noinline)) int
+foo (int *a, int *b)
+{
+ int i;
+ int *a1 = a;
+ int *a0 = a1 - 512;
+ for (i = 0; i < 50; i++)
+ {
+ *b = *a0 + *a1;
+ b--;
+ a0--;
+ a1--;
+ }
+ return 0;
+}
+
+int main (void)
+{
+ int *a = &arr[1024];
+ int *b = &arr[1022];
+
+ int i;
+ for (i = 0; i < 2048; i++)
+ arr[i] = i;
+
+ foo (a, b);
+
+ for (i = 973; i < 1020; i++)
+ if (arr[i] != res[i - 973])
+ abort ();
+
+ return 0;
+}
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index a5f8c1c..f0799d9 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1259,6 +1259,15 @@ prune_runtime_alias_test_list
(vec<dr_with_seg_len_pair_t> *alias_pairs,
!= tree_int_cst_compare (DR_STEP (dr_a2->dr), size_zero_node))
continue;
+ bool neg_step
+ = (tree_int_cst_compare (DR_STEP (dr_a1->dr), size_zero_node) < 0);
+
+ /* DR_A1 and DR_A2 must have the same step if it's negative. */
+ if (neg_step
+ && tree_int_cst_compare (DR_STEP (dr_a1->dr),
+ DR_STEP (dr_a2->dr)) != 0)
+ continue;
+
/* Make sure dr_a1 starts left of dr_a2. */
if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr)))
std::swap (*dr_a1, *dr_a2);
@@ -1266,60 +1275,101 @@ prune_runtime_alias_test_list
(vec<dr_with_seg_len_pair_t> *alias_pairs,
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)));
+ - tree_to_shwi (DR_INIT (dr_a1->dr)));
+ tree new_seg_len;
+ unsigned HOST_WIDE_INT min_seg_len_b;
- /* If the left segment does not extend beyond the start of the
- right segment the new segment length is that of the right
- plus the segment distance. */
- if (tree_fits_uhwi_p (dr_a1->seg_len)
- && compare_tree_int (dr_a1->seg_len, diff) <= 0)
+ if (tree_fits_uhwi_p (dr_b1->seg_len))
{
- dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len,
- size_int (diff));
- do_remove = true;
+ min_seg_len_b = tree_to_uhwi (dr_b1->seg_len);
+ if (tree_int_cst_sign_bit (dr_b1->seg_len))
+ min_seg_len_b = 0 - min_seg_len_b;
}
- /* Generally the new segment length is the maximum of the
- left segment size and the right segment size plus the distance.
- ??? We can also build tree MAX_EXPR here but it's not clear this
- is profitable. */
- else if (tree_fits_uhwi_p (dr_a1->seg_len)
- && tree_fits_uhwi_p (dr_a2->seg_len))
- {
- unsigned HOST_WIDE_INT seg_len_a1 = tree_to_uhwi (dr_a1->seg_len);
- unsigned HOST_WIDE_INT seg_len_a2 = tree_to_uhwi (dr_a2->seg_len);
- dr_a1->seg_len = size_int (MAX (seg_len_a1, diff + seg_len_a2));
- do_remove = true;
- }
- /* Now we check if the following condition is satisfied:
+ else
+ min_seg_len_b = factor;
- DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
+ /* Now we try to merge alias check dr_a1 & dr_b and dr_a2 & dr_b.
- 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,
- then either of the following two conditions can guarantee the
- one above:
+ Case A:
+ check if the following condition is satisfied:
- 1: DIFF <= MIN_SEG_LEN_B
- 2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B */
- else
+ DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
+
+ 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,
+ then either of the following two conditions can guarantee the
+ one above:
+
+ 1: DIFF <= MIN_SEG_LEN_B
+ 2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B
+ Because DIFF - SEGMENT_LENGTH_A is done in sizetype, we need
+ to take care of wrapping behavior in it.
+
+ Case B:
+ If the left segment does not extend beyond the start of the
+ right segment the new segment length is that of the right
+ plus the segment distance.
+
+ Note 1: Case A.2 and B combined together effectively merges every
+ dr_a1 & dr_b and dr_a2 & dr_b when SEGMENT_LENGTH_A is const. We
+ test them separately for clarity, also because Case A never
+ introduces false alias, while Case B does.
+
+ Note 2: Above description is based on positive DR_STEP, we need to
+ take care of negative DR_STEP for wrapping behavior. See PR80815
+ for more information. */
+ if (neg_step)
{
- unsigned HOST_WIDE_INT min_seg_len_b
- = (tree_fits_uhwi_p (dr_b1->seg_len)
- ? tree_to_uhwi (dr_b1->seg_len)
- : factor);
+ /* Case A. */
+ if (diff <= min_seg_len_b
+ || (tree_fits_uhwi_p (dr_a1->seg_len)
+ && (diff + tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b
+ || diff < 0 - tree_to_uhwi (dr_a1->seg_len)))
+ /* Case B. */
+ || (tree_fits_uhwi_p (dr_a1->seg_len)
+ && diff > 0 - tree_to_uhwi (dr_a1->seg_len)))
+ {
+ if (tree_fits_uhwi_p (dr_a1->seg_len)
+ && tree_fits_uhwi_p (dr_a2->seg_len))
+ new_seg_len
+ = size_int (MIN (tree_to_uhwi (dr_a1->seg_len),
+ tree_to_uhwi (dr_a2->seg_len) - diff));
+ else
+ new_seg_len = size_binop (MINUS_EXPR,
+ dr_a2->seg_len, size_int (diff));
+ dr_a2->seg_len = new_seg_len;
+ do_remove = true;
+ }
+ }
+ else
+ {
+ /* Case A. */
if (diff <= min_seg_len_b
|| (tree_fits_uhwi_p (dr_a1->seg_len)
- && diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b))
+ && (diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b
+ || diff < tree_to_uhwi (dr_a1->seg_len)))
+ /* Case B. */
+ || (tree_fits_uhwi_p (dr_a1->seg_len)
+ && diff > tree_to_uhwi (dr_a1->seg_len)))
{
- dr_a1->seg_len = size_binop (PLUS_EXPR,
- dr_a2->seg_len, size_int (diff));
+ if (tree_fits_uhwi_p (dr_a1->seg_len)
+ && tree_fits_uhwi_p (dr_a2->seg_len))
+ new_seg_len
+ = size_int (MAX (tree_to_uhwi (dr_a1->seg_len),
+ diff + tree_to_uhwi (dr_a2->seg_len)));
+ else
+ new_seg_len
+ = size_binop (PLUS_EXPR, dr_a2->seg_len, size_int (diff));
+
+ dr_a1->seg_len = new_seg_len;
do_remove = true;
}
}
+
if (do_remove)
{
if (dump_enabled_p ())
@@ -1334,7 +1384,8 @@ prune_runtime_alias_test_list
(vec<dr_with_seg_len_pair_t> *alias_pairs,
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
dump_printf (MSG_NOTE, "\n");
}
- alias_pairs->ordered_remove (i--);
+ alias_pairs->ordered_remove (neg_step ? i - 1 : i);
+ i--;
}
}
}
--
1.9.1
