Handle data dependence relations with different bases

Handle data dependence relations with different bases

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  <richard.sandiford@linaro.org>

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.

From-SVN: r250867