From cb4fe4013684c2984b309f799373837af582b24a Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Fri, 26 May 2017 14:18:26 +0000 Subject: [PATCH] re PR middle-end/80815 (wrong code because of broken runtime alias check in vectorizer) 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 * gcc.dg/vect/pr80815-1.c: New test. * gcc.dg/vect/pr80815-2.c: New test. From-SVN: r248512 --- gcc/ChangeLog | 6 ++ gcc/testsuite/ChangeLog | 6 ++ gcc/testsuite/gcc.dg/vect/pr80815-1.c | 38 +++++++ gcc/testsuite/gcc.dg/vect/pr80815-2.c | 46 +++++++++ gcc/tree-data-ref.c | 143 ++++++++++++++++++-------- 5 files changed, 194 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/ChangeLog b/gcc/ChangeLog index 882fc27cc8e..14cde6af201 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,9 @@ +2017-05-26 Bin Cheng + + PR tree-optimization/80815 + * tree-data-ref.c (prune_runtime_alias_test_list): Simplify condition + for merging runtime alias checks. Handle negative DR_STEPs. + 2017-05-26 Bin Cheng * tree-vect-data-refs.c (Operator==, comp_dr_with_seg_len_pair): diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index cd9bd14367d..5136e4ab6a5 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2017-05-26 Bin Cheng + + PR tree-optimization/80815 + * gcc.dg/vect/pr80815-1.c: New test. + * gcc.dg/vect/pr80815-2.c: New test. + 2017-05-26 Martin Liska PR ipa/80663 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 00000000000..98c06c0bb03 --- /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 00000000000..83557daa696 --- /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 2796b135e27..cfff7c2a45c 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1340,63 +1340,115 @@ prune_runtime_alias_test_list (vec *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; } } @@ -1415,7 +1467,8 @@ prune_runtime_alias_test_list (vec *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--; } } } -- 2.30.2