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

1 files changed, 367 insertions, 87 deletions

diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index b7f9a57..619a651 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -124,8 +124,7 @@ static struct datadep_stats
 } dependence_stats;
 
 static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
-					   struct data_reference *,
-					   struct data_reference *,
+					   unsigned int, unsigned int,
 					   struct loop *);
 /* Returns true iff A divides B.  */
 
@@ -145,6 +144,21 @@ int_divides_p (int a, int b)
   return ((b % a) == 0);
 }
 
+/* Return true if reference REF contains a union access.  */
+
+static bool
+ref_contains_union_access_p (tree ref)
+{
+  while (handled_component_p (ref))
+    {
+      ref = TREE_OPERAND (ref, 0);
+      if (TREE_CODE (TREE_TYPE (ref)) == UNION_TYPE
+	  || TREE_CODE (TREE_TYPE (ref)) == QUAL_UNION_TYPE)
+	return true;
+    }
+  return false;
+}
+
 
 
 /* Dump into FILE all the data references from DATAREFS.  */
@@ -434,13 +448,14 @@ dump_data_dependence_relation (FILE *outf,
       unsigned int i;
       struct loop *loopi;
 
-      for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+      subscript *sub;
+      FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr), i, sub)
 	{
 	  fprintf (outf, "  access_fn_A: ");
-	  print_generic_stmt (outf, DR_ACCESS_FN (dra, i));
+	  print_generic_stmt (outf, SUB_ACCESS_FN (sub, 0));
 	  fprintf (outf, "  access_fn_B: ");
-	  print_generic_stmt (outf, DR_ACCESS_FN (drb, i));
-	  dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
+	  print_generic_stmt (outf, SUB_ACCESS_FN (sub, 1));
+	  dump_subscript (outf, sub);
 	}
 
       fprintf (outf, "  inner loop index: %d\n", DDR_INNER_LOOP (ddr));
@@ -920,6 +935,27 @@ dr_analyze_innermost (innermost_loop_behavior *drb, tree ref,
   return true;
 }
 
+/* Return true if OP is a valid component reference for a DR access
+   function.  This accepts a subset of what handled_component_p accepts.  */
+
+static bool
+access_fn_component_p (tree op)
+{
+  switch (TREE_CODE (op))
+    {
+    case REALPART_EXPR:
+    case IMAGPART_EXPR:
+    case ARRAY_REF:
+      return true;
+
+    case COMPONENT_REF:
+      return TREE_CODE (TREE_TYPE (TREE_OPERAND (op, 0))) == RECORD_TYPE;
+
+    default:
+      return false;
+    }
+}
+
 /* Determines the base object and the list of indices of memory reference
    DR, analyzed in LOOP and instantiated in loop nest NEST.  */
 
@@ -957,7 +993,9 @@ dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
       access_fns.safe_push (integer_one_node);
     }
 
-  /* Analyze access functions of dimensions we know to be independent.  */
+  /* Analyze access functions of dimensions we know to be independent.
+     The list of component references handled here should be kept in
+     sync with access_fn_component_p.  */
   while (handled_component_p (ref))
     {
       if (TREE_CODE (ref) == ARRAY_REF)
@@ -2148,6 +2186,38 @@ dr_may_alias_p (const struct data_reference *a, const struct data_reference *b,
   return refs_may_alias_p (addr_a, addr_b);
 }
 
+/* REF_A and REF_B both satisfy access_fn_component_p.  Return true
+   if it is meaningful to compare their associated access functions
+   when checking for dependencies.  */
+
+static bool
+access_fn_components_comparable_p (tree ref_a, tree ref_b)
+{
+  /* Allow pairs of component refs from the following sets:
+
+       { REALPART_EXPR, IMAGPART_EXPR }
+       { COMPONENT_REF }
+       { ARRAY_REF }.  */
+  tree_code code_a = TREE_CODE (ref_a);
+  tree_code code_b = TREE_CODE (ref_b);
+  if (code_a == IMAGPART_EXPR)
+    code_a = REALPART_EXPR;
+  if (code_b == IMAGPART_EXPR)
+    code_b = REALPART_EXPR;
+  if (code_a != code_b)
+    return false;
+
+  if (TREE_CODE (ref_a) == COMPONENT_REF)
+    /* ??? We cannot simply use the type of operand #0 of the refs here as
+       the Fortran compiler smuggles type punning into COMPONENT_REFs.
+       Use the DECL_CONTEXT of the FIELD_DECLs instead.  */
+    return (DECL_CONTEXT (TREE_OPERAND (ref_a, 1))
+	    == DECL_CONTEXT (TREE_OPERAND (ref_b, 1)));
+
+  return types_compatible_p (TREE_TYPE (TREE_OPERAND (ref_a, 0)),
+			     TREE_TYPE (TREE_OPERAND (ref_b, 0)));
+}
+
 /* Initialize a data dependence relation between data accesses A and
    B.  NB_LOOPS is the number of loops surrounding the references: the
    size of the classic distance/direction vectors.  */
@@ -2160,11 +2230,10 @@ initialize_data_dependence_relation (struct data_reference *a,
   struct data_dependence_relation *res;
   unsigned int i;
 
-  res = XNEW (struct data_dependence_relation);
+  res = XCNEW (struct data_dependence_relation);
   DDR_A (res) = a;
   DDR_B (res) = b;
   DDR_LOOP_NEST (res).create (0);
-  DDR_REVERSED_P (res) = false;
   DDR_SUBSCRIPTS (res).create (0);
   DDR_DIR_VECTS (res).create (0);
   DDR_DIST_VECTS (res).create (0);
@@ -2182,82 +2251,277 @@ initialize_data_dependence_relation (struct data_reference *a,
       return res;
     }
 
-  /* The case where the references are exactly the same.  */
-  if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
+  unsigned int num_dimensions_a = DR_NUM_DIMENSIONS (a);
+  unsigned int num_dimensions_b = DR_NUM_DIMENSIONS (b);
+  if (num_dimensions_a == 0 || num_dimensions_b == 0)
     {
-      if ((loop_nest.exists ()
-	   && !object_address_invariant_in_loop_p (loop_nest[0],
-						   DR_BASE_OBJECT (a)))
-	  || DR_NUM_DIMENSIONS (a) == 0)
+      DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+      return res;
+    }
+
+  /* For unconstrained bases, the root (highest-indexed) subscript
+     describes a variation in the base of the original DR_REF rather
+     than a component access.  We have no type that accurately describes
+     the new DR_BASE_OBJECT (whose TREE_TYPE describes the type *after*
+     applying this subscript) so limit the search to the last real
+     component access.
+
+     E.g. for:
+
+	void
+	f (int a[][8], int b[][8])
 	{
-	  DDR_ARE_DEPENDENT (res) = chrec_dont_know;
-	  return res;
+	  for (int i = 0; i < 8; ++i)
+	    a[i * 2][0] = b[i][0];
+	}
+
+     the a and b accesses have a single ARRAY_REF component reference [0]
+     but have two subscripts.  */
+  if (DR_UNCONSTRAINED_BASE (a))
+    num_dimensions_a -= 1;
+  if (DR_UNCONSTRAINED_BASE (b))
+    num_dimensions_b -= 1;
+
+  /* These structures describe sequences of component references in
+     DR_REF (A) and DR_REF (B).  Each component reference is tied to a
+     specific access function.  */
+  struct {
+    /* The sequence starts at DR_ACCESS_FN (A, START_A) of A and
+       DR_ACCESS_FN (B, START_B) of B (inclusive) and extends to higher
+       indices.  In C notation, these are the indices of the rightmost
+       component references; e.g. for a sequence .b.c.d, the start
+       index is for .d.  */
+    unsigned int start_a;
+    unsigned int start_b;
+
+    /* The sequence contains LENGTH consecutive access functions from
+       each DR.  */
+    unsigned int length;
+
+    /* The enclosing objects for the A and B sequences respectively,
+       i.e. the objects to which DR_ACCESS_FN (A, START_A + LENGTH - 1)
+       and DR_ACCESS_FN (B, START_B + LENGTH - 1) are applied.  */
+    tree object_a;
+    tree object_b;
+  } full_seq = {}, struct_seq = {};
+
+  /* Before each iteration of the loop:
+
+     - REF_A is what you get after applying DR_ACCESS_FN (A, INDEX_A) and
+     - REF_B is what you get after applying DR_ACCESS_FN (B, INDEX_B).  */
+  unsigned int index_a = 0;
+  unsigned int index_b = 0;
+  tree ref_a = DR_REF (a);
+  tree ref_b = DR_REF (b);
+
+  /* Now walk the component references from the final DR_REFs back up to
+     the enclosing base objects.  Each component reference corresponds
+     to one access function in the DR, with access function 0 being for
+     the final DR_REF and the highest-indexed access function being the
+     one that is applied to the base of the DR.
+
+     Look for a sequence of component references whose access functions
+     are comparable (see access_fn_components_comparable_p).  If more
+     than one such sequence exists, pick the one nearest the base
+     (which is the leftmost sequence in C notation).  Store this sequence
+     in FULL_SEQ.
+
+     For example, if we have:
+
+	struct foo { struct bar s; ... } (*a)[10], (*b)[10];
+
+	A: a[0][i].s.c.d
+	B: __real b[0][i].s.e[i].f
+
+     (where d is the same type as the real component of f) then the access
+     functions would be:
+
+			 0   1   2   3
+	A:              .d  .c  .s [i]
+
+		 0   1   2   3   4   5
+	B:  __real  .f [i]  .e  .s [i]
+
+     The A0/B2 column isn't comparable, since .d is a COMPONENT_REF
+     and [i] is an ARRAY_REF.  However, the A1/B3 column contains two
+     COMPONENT_REF accesses for struct bar, so is comparable.  Likewise
+     the A2/B4 column contains two COMPONENT_REF accesses for struct foo,
+     so is comparable.  The A3/B5 column contains two ARRAY_REFs that
+     index foo[10] arrays, so is again comparable.  The sequence is
+     therefore:
+
+        A: [1, 3]  (i.e. [i].s.c)
+        B: [3, 5]  (i.e. [i].s.e)
+
+     Also look for sequences of component references whose access
+     functions are comparable and whose enclosing objects have the same
+     RECORD_TYPE.  Store this sequence in STRUCT_SEQ.  In the above
+     example, STRUCT_SEQ would be:
+
+        A: [1, 2]  (i.e. s.c)
+        B: [3, 4]  (i.e. s.e)  */
+  while (index_a < num_dimensions_a && index_b < num_dimensions_b)
+    {
+      /* REF_A and REF_B must be one of the component access types
+	 allowed by dr_analyze_indices.  */
+      gcc_checking_assert (access_fn_component_p (ref_a));
+      gcc_checking_assert (access_fn_component_p (ref_b));
+
+      /* Get the immediately-enclosing objects for REF_A and REF_B,
+	 i.e. the references *before* applying DR_ACCESS_FN (A, INDEX_A)
+	 and DR_ACCESS_FN (B, INDEX_B).  */
+      tree object_a = TREE_OPERAND (ref_a, 0);
+      tree object_b = TREE_OPERAND (ref_b, 0);
+
+      tree type_a = TREE_TYPE (object_a);
+      tree type_b = TREE_TYPE (object_b);
+      if (access_fn_components_comparable_p (ref_a, ref_b))
+	{
+	  /* This pair of component accesses is comparable for dependence
+	     analysis, so we can include DR_ACCESS_FN (A, INDEX_A) and
+	     DR_ACCESS_FN (B, INDEX_B) in the sequence.  */
+	  if (full_seq.start_a + full_seq.length != index_a
+	      || full_seq.start_b + full_seq.length != index_b)
+	    {
+	      /* The accesses don't extend the current sequence,
+		 so start a new one here.  */
+	      full_seq.start_a = index_a;
+	      full_seq.start_b = index_b;
+	      full_seq.length = 0;
+	    }
+
+	  /* Add this pair of references to the sequence.  */
+	  full_seq.length += 1;
+	  full_seq.object_a = object_a;
+	  full_seq.object_b = object_b;
+
+	  /* If the enclosing objects are structures (and thus have the
+	     same RECORD_TYPE), record the new sequence in STRUCT_SEQ.  */
+	  if (TREE_CODE (type_a) == RECORD_TYPE)
+	    struct_seq = full_seq;
+
+	  /* Move to the next containing reference for both A and B.  */
+	  ref_a = object_a;
+	  ref_b = object_b;
+	  index_a += 1;
+	  index_b += 1;
+	  continue;
+	}
+
+      /* Try to approach equal type sizes.  */
+      if (!COMPLETE_TYPE_P (type_a)
+	  || !COMPLETE_TYPE_P (type_b)
+	  || !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_a))
+	  || !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_b)))
+	break;
+
+      unsigned HOST_WIDE_INT size_a = tree_to_uhwi (TYPE_SIZE_UNIT (type_a));
+      unsigned HOST_WIDE_INT size_b = tree_to_uhwi (TYPE_SIZE_UNIT (type_b));
+      if (size_a <= size_b)
+	{
+	  index_a += 1;
+	  ref_a = object_a;
+	}
+      if (size_b <= size_a)
+	{
+	  index_b += 1;
+	  ref_b = object_b;
 	}
-      DDR_AFFINE_P (res) = true;
-      DDR_ARE_DEPENDENT (res) = NULL_TREE;
-      DDR_SUBSCRIPTS (res).create (DR_NUM_DIMENSIONS (a));
-      DDR_LOOP_NEST (res) = loop_nest;
-      DDR_INNER_LOOP (res) = 0;
-      DDR_SELF_REFERENCE (res) = true;
-      for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
-       {
-         struct subscript *subscript;
-
-         subscript = XNEW (struct subscript);
-         SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
-         SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
-         SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
-         SUB_DISTANCE (subscript) = chrec_dont_know;
-         DDR_SUBSCRIPTS (res).safe_push (subscript);
-       }
-      return res;
     }
 
-  /* If the references do not access the same object, we do not know
-     whether they alias or not.  We do not care about TBAA or alignment
-     info so we can use OEP_ADDRESS_OF to avoid false negatives.
-     But the accesses have to use compatible types as otherwise the
-     built indices would not match.  */
-  if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), OEP_ADDRESS_OF)
-      || !types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (a)),
-			      TREE_TYPE (DR_BASE_OBJECT (b))))
+  /* See whether FULL_SEQ ends at the base and whether the two bases
+     are equal.  We do not care about TBAA or alignment info so we can
+     use OEP_ADDRESS_OF to avoid false negatives.  */
+  tree base_a = DR_BASE_OBJECT (a);
+  tree base_b = DR_BASE_OBJECT (b);
+  bool same_base_p = (full_seq.start_a + full_seq.length == num_dimensions_a
+		      && full_seq.start_b + full_seq.length == num_dimensions_b
+		      && DR_UNCONSTRAINED_BASE (a) == DR_UNCONSTRAINED_BASE (b)
+		      && operand_equal_p (base_a, base_b, OEP_ADDRESS_OF)
+		      && types_compatible_p (TREE_TYPE (base_a),
+					     TREE_TYPE (base_b))
+		      && (!loop_nest.exists ()
+			  || (object_address_invariant_in_loop_p
+			      (loop_nest[0], base_a))));
+
+  /* If the bases are the same, we can include the base variation too.
+     E.g. the b accesses in:
+
+       for (int i = 0; i < n; ++i)
+         b[i + 4][0] = b[i][0];
+
+     have a definite dependence distance of 4, while for:
+
+       for (int i = 0; i < n; ++i)
+         a[i + 4][0] = b[i][0];
+
+     the dependence distance depends on the gap between a and b.
+
+     If the bases are different then we can only rely on the sequence
+     rooted at a structure access, since arrays are allowed to overlap
+     arbitrarily and change shape arbitrarily.  E.g. we treat this as
+     valid code:
+
+       int a[256];
+       ...
+       ((int (*)[4][3]) &a[1])[i][0] += ((int (*)[4][3]) &a[2])[i][0];
+
+     where two lvalues with the same int[4][3] type overlap, and where
+     both lvalues are distinct from the object's declared type.  */
+  if (same_base_p)
     {
-      DDR_ARE_DEPENDENT (res) = chrec_dont_know;
-      return res;
+      if (DR_UNCONSTRAINED_BASE (a))
+	full_seq.length += 1;
     }
+  else
+    full_seq = struct_seq;
 
-  /* If the base of the object is not invariant in the loop nest, we cannot
-     analyze it.  TODO -- in fact, it would suffice to record that there may
-     be arbitrary dependences in the loops where the base object varies.  */
-  if ((loop_nest.exists ()
-       && !object_address_invariant_in_loop_p (loop_nest[0], DR_BASE_OBJECT (a)))
-      || DR_NUM_DIMENSIONS (a) == 0)
+  /* Punt if we didn't find a suitable sequence.  */
+  if (full_seq.length == 0)
     {
       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
       return res;
     }
 
-  /* If the number of dimensions of the access to not agree we can have
-     a pointer access to a component of the array element type and an
-     array access while the base-objects are still the same.  Punt.  */
-  if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
+  if (!same_base_p)
     {
-      DDR_ARE_DEPENDENT (res) = chrec_dont_know;
-      return res;
+      /* Partial overlap is possible for different bases when strict aliasing
+	 is not in effect.  It's also possible if either base involves a union
+	 access; e.g. for:
+
+	   struct s1 { int a[2]; };
+	   struct s2 { struct s1 b; int c; };
+	   struct s3 { int d; struct s1 e; };
+	   union u { struct s2 f; struct s3 g; } *p, *q;
+
+	 the s1 at "p->f.b" (base "p->f") partially overlaps the s1 at
+	 "p->g.e" (base "p->g") and might partially overlap the s1 at
+	 "q->g.e" (base "q->g").  */
+      if (!flag_strict_aliasing
+	  || ref_contains_union_access_p (full_seq.object_a)
+	  || ref_contains_union_access_p (full_seq.object_b))
+	{
+	  DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+	  return res;
+	}
+
+      DDR_COULD_BE_INDEPENDENT_P (res) = true;
     }
 
   DDR_AFFINE_P (res) = true;
   DDR_ARE_DEPENDENT (res) = NULL_TREE;
-  DDR_SUBSCRIPTS (res).create (DR_NUM_DIMENSIONS (a));
+  DDR_SUBSCRIPTS (res).create (full_seq.length);
   DDR_LOOP_NEST (res) = loop_nest;
   DDR_INNER_LOOP (res) = 0;
   DDR_SELF_REFERENCE (res) = false;
 
-  for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
+  for (i = 0; i < full_seq.length; ++i)
     {
       struct subscript *subscript;
 
       subscript = XNEW (struct subscript);
+      SUB_ACCESS_FN (subscript, 0) = DR_ACCESS_FN (a, full_seq.start_a + i);
+      SUB_ACCESS_FN (subscript, 1) = DR_ACCESS_FN (b, full_seq.start_b + i);
       SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
       SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
@@ -3839,14 +4103,15 @@ add_outer_distances (struct data_dependence_relation *ddr,
 }
 
 /* Return false when fail to represent the data dependence as a
-   distance vector.  INIT_B is set to true when a component has been
+   distance vector.  A_INDEX is the index of the first reference
+   (0 for DDR_A, 1 for DDR_B) and B_INDEX is the index of the
+   second reference.  INIT_B is set to true when a component has been
    added to the distance vector DIST_V.  INDEX_CARRY is then set to
    the index in DIST_V that carries the dependence.  */
 
 static bool
 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
-			     struct data_reference *ddr_a,
-			     struct data_reference *ddr_b,
+			     unsigned int a_index, unsigned int b_index,
 			     lambda_vector dist_v, bool *init_b,
 			     int *index_carry)
 {
@@ -3864,8 +4129,8 @@ build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
 	  return false;
 	}
 
-      access_fn_a = DR_ACCESS_FN (ddr_a, i);
-      access_fn_b = DR_ACCESS_FN (ddr_b, i);
+      access_fn_a = SUB_ACCESS_FN (subscript, a_index);
+      access_fn_b = SUB_ACCESS_FN (subscript, b_index);
 
       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
 	  && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
@@ -3925,10 +4190,11 @@ static bool
 constant_access_functions (const struct data_dependence_relation *ddr)
 {
   unsigned i;
+  subscript *sub;
 
-  for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
-    if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
-	|| !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
+  FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr), i, sub)
+    if (!evolution_function_is_constant_p (SUB_ACCESS_FN (sub, 0))
+	|| !evolution_function_is_constant_p (SUB_ACCESS_FN (sub, 1)))
       return false;
 
   return true;
@@ -3991,10 +4257,11 @@ add_other_self_distances (struct data_dependence_relation *ddr)
   lambda_vector dist_v;
   unsigned i;
   int index_carry = DDR_NB_LOOPS (ddr);
+  subscript *sub;
 
-  for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+  FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr), i, sub)
     {
-      tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
+      tree access_fun = SUB_ACCESS_FN (sub, 0);
 
       if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
 	{
@@ -4006,7 +4273,7 @@ add_other_self_distances (struct data_dependence_relation *ddr)
 		  return;
 		}
 
-	      access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
+	      access_fun = SUB_ACCESS_FN (DDR_SUBSCRIPT (ddr, 0), 0);
 
 	      if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
 		add_multivariate_self_dist (ddr, access_fun);
@@ -4077,6 +4344,23 @@ add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
     }
 }
 
+/* Return true when the DDR contains two data references that have the
+   same access functions.  */
+
+static inline bool
+same_access_functions (const struct data_dependence_relation *ddr)
+{
+  unsigned i;
+  subscript *sub;
+
+  FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr), i, sub)
+    if (!eq_evolutions_p (SUB_ACCESS_FN (sub, 0),
+			  SUB_ACCESS_FN (sub, 1)))
+      return false;
+
+  return true;
+}
+
 /* Compute the classic per loop distance vector.  DDR is the data
    dependence relation to build a vector from.  Return false when fail
    to represent the data dependence as a distance vector.  */
@@ -4108,8 +4392,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
     }
 
   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
-  if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
-				    dist_v, &init_b, &index_carry))
+  if (!build_classic_dist_vector_1 (ddr, 0, 1, dist_v, &init_b, &index_carry))
     return false;
 
   /* Save the distance vector if we initialized one.  */
@@ -4142,12 +4425,11 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
       if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
 	{
 	  lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
-	  if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
-					      loop_nest))
+	  if (!subscript_dependence_tester_1 (ddr, 1, 0, loop_nest))
 	    return false;
 	  compute_subscript_distance (ddr);
-	  if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
-					    save_v, &init_b, &index_carry))
+	  if (!build_classic_dist_vector_1 (ddr, 1, 0, save_v, &init_b,
+					    &index_carry))
 	    return false;
 	  save_dist_v (ddr, save_v);
 	  DDR_REVERSED_P (ddr) = true;
@@ -4183,12 +4465,10 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
 	    {
 	      lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
 
-	      if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
-						  DDR_A (ddr), loop_nest))
+	      if (!subscript_dependence_tester_1 (ddr, 1, 0, loop_nest))
 		return false;
 	      compute_subscript_distance (ddr);
-	      if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
-						opposite_v, &init_b,
+	      if (!build_classic_dist_vector_1 (ddr, 1, 0, opposite_v, &init_b,
 						&index_carry))
 		return false;
 
@@ -4267,13 +4547,13 @@ build_classic_dir_vector (struct data_dependence_relation *ddr)
     }
 }
 
-/* Helper function.  Returns true when there is a dependence between
-   data references DRA and DRB.  */
+/* Helper function.  Returns true when there is a dependence between the
+   data references.  A_INDEX is the index of the first reference (0 for
+   DDR_A, 1 for DDR_B) and B_INDEX is the index of the second reference.  */
 
 static bool
 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
-			       struct data_reference *dra,
-			       struct data_reference *drb,
+			       unsigned int a_index, unsigned int b_index,
 			       struct loop *loop_nest)
 {
   unsigned int i;
@@ -4285,8 +4565,8 @@ subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
     {
       conflict_function *overlaps_a, *overlaps_b;
 
-      analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
-				      DR_ACCESS_FN (drb, i),
+      analyze_overlapping_iterations (SUB_ACCESS_FN (subscript, a_index),
+				      SUB_ACCESS_FN (subscript, b_index),
 				      &overlaps_a, &overlaps_b,
 				      &last_conflicts, loop_nest);
 
@@ -4335,7 +4615,7 @@ static void
 subscript_dependence_tester (struct data_dependence_relation *ddr,
 			     struct loop *loop_nest)
 {
-  if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
+  if (subscript_dependence_tester_1 (ddr, 0, 1, loop_nest))
     dependence_stats.num_dependence_dependent++;
 
   compute_subscript_distance (ddr);