Handle data dependence relations with different bases

Programming / Compilers / GCC - rsandifo [138bc75d-0d04-0410-961f-82ee72b054a4] - 4 August 2017 06:39 EDT

This patch tries to calculate conservatively-correct distance
vectors for two references whose base addresses are not the same. It sets a new flag DDR_COULD_BE_INDEPENDENT_P if the dependence isn't guaranteed to occur.

The motivating example is:

struct s { int x[8]; };
void f (struct s *a, struct s *b) { for (int i = 0; i < 8; ++i) a->x[i] += b->x[i]; }

in which the "a" and "b" accesses are either independent or have a dependence distance of 0 (assuming -fstrict-aliasing). Neither case prevents vectorisation, so we can vectorise without an alias check.

I'd originally wanted to do the same thing for arrays as well, e.g.:

void f (int a[][8], struct b[][8]) { for (int i = 0; i < 8; ++i) a[0][i] += b[0][i]; }

I think this is valid because C11 6.7.6.2/6 says:

For two array types to be compatible, both shall have compatible element types, and if both size specifiers are present, and are integer constant expressions, then both size specifiers shall have the same constant value.

So if we access an array through an int (*)[8], it must have type X[8] or X[], where X is compatible with int. It doesn't seem possible in either case for "a[0]" and "b[0]" to overlap when "a != b".

However, as the comment above "if (same_base_p)" explains, GCC is more forgiving: it supports arbitrary overlap of arrays and allows arrays to be accessed with different dimensionality. There are examples of this in PR50067. The patch therefore only handles references that end in a structure field access.

There are two ways of handling these dependences in the vectoriser: use them to limit VF, or check at runtime as before. I've gone for the approach of checking at runtime if we can, to avoid limiting VF unnecessarily, but falling back to a VF cap when runtime checks aren't allowed.

The patch tests whether we queued an alias check with a dependence distance of X and then picked a VF <= X, in which case it's safe to drop the alias check. Since vect_prune_runtime_alias_check_list can be called twice with different VF for the same loop, it's no longer safe to clear may_alias_ddrs on exit. Instead we should use comp_alias_ddrs to check whether versioning is necessary.

2017-08-04 Richard Sandiford

gcc/
- tree-data-ref.h (subscript): Add access_fn field. (data_dependence_relation): Add could_be_independent_p. (SUB_ACCESS_FN, DDR_COULD_BE_INDEPENDENT_P): New macros. (same_access_functions): Move to tree-data-ref.c.
- tree-data-ref.c (ref_contains_union_access_p): New function. (access_fn_component_p): Likewise. (access_fn_components_comparable_p): Likewise. (dr_analyze_indices): Add a reference to access_fn_component_p. (dump_data_dependence_relation): Use SUB_ACCESS_FN instead of DR_ACCESS_FN. (constant_access_functions): Likewise. (add_other_self_distances): Likewise. (same_access_functions): Likewise. (Moved from tree-data-ref.h.) (initialize_data_dependence_relation): Use XCNEW and remove explicit zeroing of DDR_REVERSED_P. Look for a subsequence of access functions that have the same type. Allow the subsequence to end with different bases in some circumstances. Record the chosen access functions in SUB_ACCESS_FN. (build_classic_dist_vector_1): Replace ddr_a and ddr_b with a_index and b_index. Use SUB_ACCESS_FN instead of DR_ACCESS_FN. (subscript_dependence_tester_1): Likewise dra and drb. (build_classic_dist_vector): Update calls accordingly. (subscript_dependence_tester): Likewise.
- tree-ssa-loop-prefetch.c (determine_loop_nest_reuse): Check DDR_COULD_BE_INDEPENDENT_P.
- tree-vectorizer.h (LOOP_REQUIRES_VERSIONING_FOR_ALIAS): Test comp_alias_ddrs instead of may_alias_ddrs.
- tree-vect-data-refs.c (vect_analyze_possibly_independent_ddr): New function. (vect_analyze_data_ref_dependence): Use it if DDR_COULD_BE_INDEPENDENT_P, but fall back to using the recorded distance vectors if that fails. (dependence_distance_ge_vf): New function. (vect_prune_runtime_alias_test_list): Use it. Don't clear LOOP_VINFO_MAY_ALIAS_DDRS.

gcc/testsuite/
- gcc.dg/vect/vect-alias-check-3.c: New test.
- gcc.dg/vect/vect-alias-check-4.c: Likewise.
- gcc.dg/vect/vect-alias-check-5.c: Likewise.

403965f Handle data dependence relations with different bases
gcc/ChangeLog | 38 +++
gcc/testsuite/ChangeLog | 6 +
gcc/testsuite/gcc.dg/vect/vect-alias-check-3.c | 120 +++++++
gcc/testsuite/gcc.dg/vect/vect-alias-check-4.c | 35 ++
gcc/testsuite/gcc.dg/vect/vect-alias-check-5.c | 19 ++
gcc/tree-data-ref.c | 454 ++++++++++++++++++++-----
gcc/tree-data-ref.h | 48 ++-
gcc/tree-ssa-loop-prefetch.c | 1 +
gcc/tree-vect-data-refs.c | 111 +++++-
gcc/tree-vectorizer.h | 2 +-
10 files changed, 726 insertions(+), 108 deletions(-)

Upstream: gcc.gnu.org


  • Share