From 6fa3d4b4a75e63276f5460a59395e1d3a634c477 Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Wed, 13 Jul 2016 15:06:40 +0000 Subject: [PATCH] tree-vect-data-refs.c (vect_no_alias_p): New function. * tree-vect-data-refs.c (vect_no_alias_p): New function. (vect_prune_runtime_alias_test_list): Call vect_no_alias_p to resolve alias checks which are known at compilation time. Truncate vector LOOP_VINFO_MAY_ALIAS_DDRS(loop_vinfo) if all alias checks are resolved. Move dump info for too many runtime alias checks to here... * tree-vect-loop.c (vect_analyze_loop_2): ...From here. gcc/testsuite * gcc.dg/vect/vect-35-big-array.c: Refine comment and test. * gcc.dg/vect/vect-35.c: Ditto. * gcc.dg/vect/vect-alias-check-2.c: New test. From-SVN: r238301 --- gcc/ChangeLog | 10 +++ gcc/testsuite/ChangeLog | 6 ++ gcc/testsuite/gcc.dg/vect/vect-35-big-array.c | 8 ++- gcc/testsuite/gcc.dg/vect/vect-35.c | 6 +- gcc/testsuite/gcc.dg/vect/vect-alias-check-2.c | 19 ++++++ gcc/tree-vect-data-refs.c | 90 ++++++++++++++++++++++++-- gcc/tree-vect-loop.c | 10 +-- 7 files changed, 130 insertions(+), 19 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/vect/vect-alias-check-2.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index cd416b7..2862d0e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,13 @@ +2016-07-13 Bin Cheng + + * tree-vect-data-refs.c (vect_no_alias_p): New function. + (vect_prune_runtime_alias_test_list): Call vect_no_alias_p to + resolve alias checks which are known at compilation time. + Truncate vector LOOP_VINFO_MAY_ALIAS_DDRS(loop_vinfo) if all + alias checks are resolved. Move dump info for too many runtime + alias checks to here... + * tree-vect-loop.c (vect_analyze_loop_2): ...From here. + 2016-07-13 Richard Biener PR tree-optimization/24574 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 321957e..f868af3 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2016-07-13 Bin Cheng + + * gcc.dg/vect/vect-35-big-array.c: Refine comment and test. + * gcc.dg/vect/vect-35.c: Ditto. + * gcc.dg/vect/vect-alias-check-2.c: New test. + 2016-07-13 Martin Liska * gfortran.dg/ldist-1.f90: Revert change introduces in r238114. diff --git a/gcc/testsuite/gcc.dg/vect/vect-35-big-array.c b/gcc/testsuite/gcc.dg/vect/vect-35-big-array.c index 1caca74..ca57a10 100644 --- a/gcc/testsuite/gcc.dg/vect/vect-35-big-array.c +++ b/gcc/testsuite/gcc.dg/vect/vect-35-big-array.c @@ -21,7 +21,9 @@ int main1 () } /* Dependence analysis fails cause s.a and s.b may overlap. - Use runtime aliasing test with versioning. */ + Try to use runtime aliasing test with versioning, and + later versioning/vectorization are skipped because the + overlap is proven at compilation time. */ for (i = 0; i < N; i++) { s.a[i] = s.b[i] + 1; @@ -45,5 +47,5 @@ int main (void) } -/* { dg-final { scan-tree-dump-times "vectorized 2 loops" 1 "vect" { xfail { ia64-*-* sparc*-*-* } } } } */ -/* { dg-final { scan-tree-dump-times "can't determine dependence between" 1 "vect" } } */ +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail { ia64-*-* sparc*-*-* } } } } */ +/* { dg-final { scan-tree-dump "can't determine dependence between" "vect" } } */ diff --git a/gcc/testsuite/gcc.dg/vect/vect-35.c b/gcc/testsuite/gcc.dg/vect/vect-35.c index edbeb1f..76fe32d 100644 --- a/gcc/testsuite/gcc.dg/vect/vect-35.c +++ b/gcc/testsuite/gcc.dg/vect/vect-35.c @@ -21,7 +21,9 @@ int main1 () } /* Dependence analysis fails cause s.a and s.b may overlap. - Use runtime aliasing test with versioning. */ + Try to use runtime aliasing test with versioning, and + later versioning/vectorization are skipped because the + overlap is proven at compilation time. */ for (i = 0; i < N; i++) { s.a[i] = s.b[i] + 1; @@ -45,5 +47,5 @@ int main (void) } -/* { dg-final { scan-tree-dump-times "vectorized 2 loops" 1 "vect" { xfail { ia64-*-* sparc*-*-* } } } } */ +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail { ia64-*-* sparc*-*-* } } } } */ /* { dg-final { scan-tree-dump "can't determine dependence between" "vect" } } */ diff --git a/gcc/testsuite/gcc.dg/vect/vect-alias-check-2.c b/gcc/testsuite/gcc.dg/vect/vect-alias-check-2.c new file mode 100644 index 0000000..1163314 --- /dev/null +++ b/gcc/testsuite/gcc.dg/vect/vect-alias-check-2.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target vect_int_mult } */ + +int a [128]; +int b[128] = {0}; + +int foo (void) +{ + int k; + + for(k=0; k<64; k++) + { + b[k] = 10 - b[127-k]; + a[k] = b[k] * 3; + a[127-k] = b[127-k] * 2; + } +} + +/* { dg-final { scan-tree-dump-not "versioning for alias checks." "vect" } } */ diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c index 353d1df..9a5408e 100644 --- a/gcc/tree-vect-data-refs.c +++ b/gcc/tree-vect-data-refs.c @@ -2938,6 +2938,56 @@ vect_vfa_segment_size (struct data_reference *dr, tree length_factor) return segment_length; } +/* Function vect_no_alias_p. + + Given data references A and B with equal base and offset, the alias + relation can be decided at compilation time, return TRUE if they do + not alias to each other; return FALSE otherwise. SEGMENT_LENGTH_A + and SEGMENT_LENGTH_B are the memory lengths accessed by A and B + respectively. */ + +static bool +vect_no_alias_p (struct data_reference *a, struct data_reference *b, + tree segment_length_a, tree segment_length_b) +{ + gcc_assert (TREE_CODE (DR_INIT (a)) == INTEGER_CST + && TREE_CODE (DR_INIT (b)) == INTEGER_CST); + if (tree_int_cst_equal (DR_INIT (a), DR_INIT (b))) + return false; + + tree seg_a_min = DR_INIT (a); + tree seg_a_max = fold_build2 (PLUS_EXPR, TREE_TYPE (seg_a_min), + seg_a_min, segment_length_a); + /* For negative step, we need to adjust address range by TYPE_SIZE_UNIT + bytes, e.g., int a[3] -> a[1] range is [a+4, a+16) instead of + [a, a+12) */ + if (tree_int_cst_compare (DR_STEP (a), size_zero_node) < 0) + { + tree unit_size = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (a))); + seg_a_min = fold_build2 (PLUS_EXPR, TREE_TYPE (seg_a_max), + seg_a_max, unit_size); + seg_a_max = fold_build2 (PLUS_EXPR, TREE_TYPE (DR_INIT (a)), + DR_INIT (a), unit_size); + } + tree seg_b_min = DR_INIT (b); + tree seg_b_max = fold_build2 (PLUS_EXPR, TREE_TYPE (seg_b_min), + seg_b_min, segment_length_b); + if (tree_int_cst_compare (DR_STEP (b), size_zero_node) < 0) + { + tree unit_size = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (b))); + seg_b_min = fold_build2 (PLUS_EXPR, TREE_TYPE (seg_b_max), + seg_b_max, unit_size); + seg_b_max = fold_build2 (PLUS_EXPR, TREE_TYPE (DR_INIT (b)), + DR_INIT (b), unit_size); + } + + if (tree_int_cst_le (seg_a_max, seg_b_min) + || tree_int_cst_le (seg_b_max, seg_a_min)) + return true; + + return false; +} + /* Function vect_prune_runtime_alias_test_list. Prune a list of ddrs to be tested at run-time by versioning for alias. @@ -3030,15 +3080,33 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo) segment_length_a = vect_vfa_segment_size (dr_a, length_factor); segment_length_b = vect_vfa_segment_size (dr_b, length_factor); + comp_res = compare_tree (DR_BASE_ADDRESS (dr_a), DR_BASE_ADDRESS (dr_b)); + if (comp_res == 0) + comp_res = compare_tree (DR_OFFSET (dr_a), DR_OFFSET (dr_b)); + + /* Alias is known at compilation time. */ + if (comp_res == 0 + && TREE_CODE (DR_STEP (dr_a)) == INTEGER_CST + && TREE_CODE (DR_STEP (dr_b)) == INTEGER_CST + && TREE_CODE (segment_length_a) == INTEGER_CST + && TREE_CODE (segment_length_b) == INTEGER_CST) + { + if (vect_no_alias_p (dr_a, dr_b, segment_length_a, segment_length_b)) + continue; + + if (dump_enabled_p ()) + dump_printf_loc (MSG_NOTE, vect_location, + "not vectorized: compilation time alias.\n"); + + return false; + } + dr_with_seg_len_pair_t dr_with_seg_len_pair (dr_with_seg_len (dr_a, segment_length_a), dr_with_seg_len (dr_b, segment_length_b)); /* 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)) + if (comp_res > 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); @@ -3187,7 +3255,19 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo) may_alias_ddrs.length (), comp_alias_ddrs.length ()); if ((int) comp_alias_ddrs.length () > PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS)) - return false; + { + if (dump_enabled_p ()) + dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, + "number of versioning for alias " + "run-time tests exceeds %d " + "(--param vect-max-version-for-alias-checks)\n", + PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS)); + return false; + } + + /* All alias checks have been resolved at compilation time. */ + if (!comp_alias_ddrs.length ()) + LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo).truncate (0); return true; } diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c index 97acf3c..11863af 100644 --- a/gcc/tree-vect-loop.c +++ b/gcc/tree-vect-loop.c @@ -1961,15 +1961,7 @@ start_over: since we use grouping information gathered by interleaving analysis. */ ok = vect_prune_runtime_alias_test_list (loop_vinfo); if (!ok) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, - "number of versioning for alias " - "run-time tests exceeds %d " - "(--param vect-max-version-for-alias-checks)\n", - PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS)); - return false; - } + return false; /* This pass will decide on using loop versioning and/or loop peeling in order to enhance the alignment of data references in the loop. */ -- 2.7.4