| Message ID | VI1PR0802MB2176A0FA67956247E4503D5DE7F90@VI1PR0802MB2176.eurprd08.prod.outlook.com |
|---|---|
| State | New |
| Headers | show |
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? 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?] > /* 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 instead, so that all arithmetic and comparisons happen in the precision of sizetype. The situation seems very close to RTL in the sense that the segment length has no inherent sign and we have to instead get the sign from the DR_STEP. Unless we can change that of course... > > ! /* 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. > ! > ! 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) > { > ! /* 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))) a2 is to the right of a1, and both segment lengths are conceptually negative, so I think this should be using dr_a2->seg_len instead of dr_a1->seg_len. E.g. for A.2, A2's segment overlaps A1's if diff < 0 - tree_to_uhwi (dr_a2->seg_len) TBH, given that the comment has already explained why this reduces to: (diff <= min_seg_len_b || TREE_CODE (dr_a2(?)->seg_len) == INTEGER_CST) I think it'd better just to write that. The clarity kind-of belongs in the comments instead. > ! { > ! 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))) > ! /* Case B. */ > ! || (tree_fits_uhwi_p (dr_a1->seg_len) > ! && diff > 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 (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,1340 **** > dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr)); > dump_printf (MSG_NOTE, "\n"); > } > ! alias_pairs->ordered_remove (i--); > } > } > } > - - > --- 1384,1391 ---- > dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr)); > dump_printf (MSG_NOTE, "\n"); > } > ! alias_pairs->ordered_remove (neg_step ? i - 1 : i); > ! i--; > } > } > }
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--; } } }
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.cheng@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.cheng@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 <binche01@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