On Wed, May 24, 2017 at 11:54 AM, Richard Sandiford
<richard.sandif...@linaro.org> wrote:
> "Bin.Cheng" <amker.ch...@gmail.com> writes:
>> On Tue, May 23, 2017 at 6:53 PM, Richard Sandiford
>> <richard.sandif...@linaro.org> wrote:
>>> AIUI, the reason the old code mishandled negative steps was that the
>>> associated segment lengths were stored as sizetype and so looked like
>>> big unsigned values. Those values therefore satisfied tree_fits_uhwi_p
>>> even though they were semantically negative. Is that right?
>> Yes, and the undesired wrapping behavior when such large unsigned hwi
>> is involved in computation. But I think there are possible leaks in
>> the code even after this patch, as embedded below.
>>>
>>> Assuming yes, and quoting the change as a context diff...
>>>
>>>> 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,1264 ****
>>>> --- 1259,1273 ----
>>>> != 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;
>>>> +
>>>
>>> [Why do they need to be the same step?]
>> There are two reasons. First is to simplify diff computation between
>> dr_a1 and dr_a2, otherwise we need to adjust diff for negative steps.
>
> What kind of adjustment would be needed? Could you give an example?
I handled negative step in updated patch by adjusting diff according
to access size of references.
>
>> And wrapping behavior needs to be handled when adjusting diff with
>> steps. The second reason is not fully handled in this patch. We now
>> only set merged segment length to MAX only when both dr_a1->seg_len
>> and dr_a2->seg_len are constant, as below:
>> + 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));
>> In fact, we should do this for else branch too. with different steps,
>> it is still possible that dr_a1-seg_len > dr_a2->seg_len + diff. Here
>> I only restrict it to negative DR_STEP. Patch updated with
>> explanation in comment.
>>>
>>>> /* 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,1325 ****
>>>> 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
>>>> ! plus the segment distance. */
>>>> ! if (tree_fits_uhwi_p (dr_a1->seg_len)
>>>> ! && compare_tree_int (dr_a1->seg_len, diff) <= 0)
>>>> {
>>>> ! dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len,
>>>> ! size_int (diff));
>>>> ! do_remove = true;
>>>> }
>>>> ! /* 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:
>>>>
>>>> ! 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 */
>>>> ! else
>>>> {
>>>> ! unsigned HOST_WIDE_INT min_seg_len_b
>>>> ! = (tree_fits_uhwi_p (dr_b1->seg_len)
>>>> ! ? tree_to_uhwi (dr_b1->seg_len)
>>>> ! : factor);
>>>>
>>>> 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))
>>>> {
>>>> ! dr_a1->seg_len = size_binop (PLUS_EXPR,
>>>> ! dr_a2->seg_len, size_int
>>>> (diff));
>>>> do_remove = true;
>>>> }
>>>> }
>>>>
>>>> if (do_remove)
>>>> {
>>>> if (dump_enabled_p ())
>>>> --- 1275,1375 ----
>>>> 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 new_seg_len;
>>>> ! unsigned HOST_WIDE_INT min_seg_len_b;
>>>>
>>>> ! if (tree_fits_uhwi_p (dr_b1->seg_len))
>>>> {
>>>> ! 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;
>>>> }
>>>> ! else
>>>> ! min_seg_len_b = factor;
>>>
>>> ...I'm not sure how safe this or the later neg_step handling is
>>> for 16-bit and 32-bit sizetypes. It might be better to use wide_int
>> I think it could be a problem in case sizetype is smaller than
>> unsigned_type_for(ptr).
>
> But I think it would a problem even for "normal" 32-bit and 16-bit
> targets, because you're doing uhwi (i.e. 64-bit) negation on things that
> come from 32-bit and 16-bit unsigned values. E.g. a segment length of
> -32 on a 32-bit target would be 0xffffffe0. If you read that as a uhwi
> and negate it, you get 0xffffffff00000020 rather than 32.
>
> Using wide_ints would avoid that. I don't think the existing code
> needed it (because the existing code didn't handle negative steps
> properly at all).
Right, patch updated using wide_int to compare diff and compute merged
segment length.
Bootstrap and test on x86_64 and AArch64.
Thanks,
bin
>
>>> instead, so that all arithmetic and comparisons happen in the precision
>>> of sizetype.
>> I was trying to make minimal refactoring for fixing the negative step
>> issue. Also I guess your SVE patches will rewrite this part entirely?
>
> Not sure TBH :-) I'll have to see how it works out when I merge it in.
>
> Thanks,
> Richard
From a31c45912c6b3621f926106a734087837e8e901e 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-20170520.txt
---
gcc/testsuite/gcc.dg/vect/pr80815-1.c | 38 +++++++++
gcc/testsuite/gcc.dg/vect/pr80815-2.c | 46 +++++++++++
gcc/tree-data-ref.c | 143 +++++++++++++++++++++++-----------
3 files changed, 182 insertions(+), 45 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..1a28000 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1259,63 +1259,115 @@ 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);
+
+ /* We need to compute merged segment length at compilation time for
+ dr_a1 and dr_a2, which is impossible if either one has non-const
+ segment length. */
+ if ((!tree_fits_uhwi_p (dr_a1->seg_len)
+ || !tree_fits_uhwi_p (dr_a2->seg_len))
+ && 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);
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
- plus the segment distance. */
- if (tree_fits_uhwi_p (dr_a1->seg_len)
- && compare_tree_int (dr_a1->seg_len, diff) <= 0)
- {
- dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len,
- size_int (diff));
- do_remove = true;
- }
- /* 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))
+ wide_int diff = wi::sub (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr));
+ wide_int min_seg_len_b;
+ tree new_seg_len;
+
+ if (tree_fits_uhwi_p (dr_b1->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;
+ min_seg_len_b = dr_b1->seg_len;
+ if (tree_int_cst_sign_bit (dr_b1->seg_len))
+ min_seg_len_b = wi::neg (min_seg_len_b);
}
- /* Now we check if the following condition is satisfied:
+ else
+ min_seg_len_b = wi::uhwi (factor, TYPE_PRECISION (sizetype));
+
+ /* Now we try to merge alias check dr_a1 & dr_b and dr_a2 & dr_b.
+
+ Case A:
+ check if the following condition is satisfied:
+
+ 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.
- DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
+ 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. The condition is like:
- 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:
+ DIFF >= SEGMENT_LENGTH_A ;SEGMENT_LENGTH_A is a constant.
- 1: DIFF <= MIN_SEG_LEN_B
- 2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B */
+ 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.
+
+ 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)
+ {
+ /* Adjust diff according to access size of both references. */
+ tree size_a1 = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a1->dr)));
+ tree size_a2 = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a2->dr)));
+ diff = wi::add (diff, wi::sub (size_a2, size_a1));
+ /* Case A.1. */
+ if (wi::leu_p (diff, min_seg_len_b)
+ /* Case A.2 and B combined. */
+ || (tree_fits_uhwi_p (dr_a2->seg_len)))
+ {
+ if (tree_fits_uhwi_p (dr_a1->seg_len)
+ && tree_fits_uhwi_p (dr_a2->seg_len))
+ new_seg_len
+ = wide_int_to_tree (sizetype,
+ wi::umin (wi::sub (dr_a1->seg_len,
+ diff),
+ dr_a2->seg_len));
+ else
+ new_seg_len
+ = size_binop (MINUS_EXPR, dr_a2->seg_len,
+ wide_int_to_tree (sizetype, diff));
+
+ dr_a2->seg_len = new_seg_len;
+ do_remove = true;
+ }
+ }
else
{
- unsigned HOST_WIDE_INT min_seg_len_b
- = (tree_fits_uhwi_p (dr_b1->seg_len)
- ? tree_to_uhwi (dr_b1->seg_len)
- : factor);
-
- 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))
+ /* Case A.1. */
+ if (wi::leu_p (diff, min_seg_len_b)
+ /* Case A.2 and B combined. */
+ || (tree_fits_uhwi_p (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
+ = wide_int_to_tree (sizetype,
+ wi::umax (wi::add (dr_a2->seg_len,
+ diff),
+ dr_a1->seg_len));
+ else
+ new_seg_len
+ = size_binop (PLUS_EXPR, dr_a2->seg_len,
+ wide_int_to_tree (sizetype, diff));
+
+ dr_a1->seg_len = new_seg_len;
do_remove = true;
}
}
@@ -1334,7 +1386,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
