Index: gcc/tree-data-ref.h
===================================================================
--- gcc/tree-data-ref.h	2017-05-03 08:48:11.977015306 +0100
+++ gcc/tree-data-ref.h	2017-05-03 08:48:48.737038502 +0100
@@ -191,6 +191,9 @@ struct conflict_function
 
 struct subscript
 {
+  /* The access functions of the two references.  */
+  tree access_fn[2];
+
   /* A description of the iterations for which the elements are
      accessed twice.  */
   conflict_function *conflicting_iterations_in_a;
@@ -209,6 +212,7 @@ struct subscript
 
 typedef struct subscript *subscript_p;
 
+#define SUB_ACCESS_FN(SUB, I) (SUB)->access_fn[I]
 #define SUB_CONFLICTS_IN_A(SUB) (SUB)->conflicting_iterations_in_a
 #define SUB_CONFLICTS_IN_B(SUB) (SUB)->conflicting_iterations_in_b
 #define SUB_LAST_CONFLICT(SUB) (SUB)->last_conflict
@@ -264,6 +268,33 @@ struct data_dependence_relation
   /* Set to true when the dependence relation is on the same data
      access.  */
   bool self_reference_p;
+
+  /* True if the dependence described is conservatively correct rather
+     than exact, and if it is still possible for the accesses to be
+     conditionally independent.  For example, the a and b references in:
+
+       struct s *a, *b;
+       for (int i = 0; i < n; ++i)
+         a->f[i] += b->f[i];
+
+     conservatively have a distance vector of (0), for the case in which
+     a == b, but the accesses are independent if a != b.  Similarly,
+     the a and b references in:
+
+       struct s *a, *b;
+       for (int i = 0; i < n; ++i)
+         a[0].f[i] += b[i].f[i];
+
+     conservatively have a distance vector of (0), but they are indepenent
+     when a != b + i.  In contrast, the references in:
+
+       struct s *a;
+       for (int i = 0; i < n; ++i)
+         a->f[i] += a->f[i];
+
+     have the same distance vector of (0), but the accesses can never be
+     independent.  */
+  bool could_be_independent_p;
 };
 
 typedef struct data_dependence_relation *ddr_p;
@@ -294,6 +325,7 @@ #define DDR_DIR_VECT(DDR, I) \
 #define DDR_DIST_VECT(DDR, I) \
   DDR_DIST_VECTS (DDR)[I]
 #define DDR_REVERSED_P(DDR) (DDR)->reversed_p
+#define DDR_COULD_BE_INDEPENDENT_P(DDR) (DDR)->could_be_independent_p
 
 
 bool dr_analyze_innermost (struct data_reference *, struct loop *);
@@ -372,22 +404,6 @@ same_data_refs (data_reference_p a, data
       return false;
 
   return true;
-}
-
-/* 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;
-
-  for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
-    if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
-			  DR_ACCESS_FN (DDR_B (ddr), i)))
-      return false;
-
-  return true;
 }
 
 /* Returns true when all the dependences are computable.  */
Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c	2017-02-23 19:54:15.000000000 +0000
+++ gcc/tree-data-ref.c	2017-05-03 08:48:48.737038502 +0100
@@ -123,8 +123,7 @@ Software Foundation; either version 3, o
 } 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.  */
 
@@ -144,6 +143,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.  */
@@ -433,13 +447,14 @@ dump_data_dependence_relation (FILE *out
       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), 0);
+	  print_generic_stmt (outf, SUB_ACCESS_FN (sub, 0), 0);
 	  fprintf (outf, "  access_fn_B: ");
-	  print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
-	  dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
+	  print_generic_stmt (outf, SUB_ACCESS_FN (sub, 1), 0);
+	  dump_subscript (outf, sub);
 	}
 
       fprintf (outf, "  inner loop index: %d\n", DDR_INNER_LOOP (ddr));
@@ -1484,11 +1499,10 @@ initialize_data_dependence_relation (str
   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);
@@ -1506,82 +1520,217 @@ initialize_data_dependence_relation (str
       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;
-	}
-      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;
+      DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+      return res;
+    }
+
+  /* For unconstrained bases, the outer (highest-index) 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 the outer subscript) so limit the search to the last real
+     component access.
+
+     E.g. for:
 
-         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);
+       void
+       f (int a[][8], int b[][8])
+       {
+	 for (int i = 0; i < 8; ++i)
+	   a[i * 2][0] = b[i][0];
        }
-      return res;
+
+     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;
+
+  /* Now look for two sequences of component references that have the same
+     type in both A and B.  The first sequence includes an arbitrary mixture
+     of array and structure references while the second always ends on a
+     structure reference.
+
+     The former (arbitrary) sequence uses access functions:
+
+        [START_A, START_A + NUM_DIMENSIONS) of A
+        [START_B, START_B + NUM_DIMENSIONS) of B
+
+     The latter sequence uses access functions:
+
+        [STRUCT_START_A, STRUCT_START_A + STRUCT_NUM_DIMENSIONS) of A
+        [STRUCT_START_B, STRUCT_START_B + STRUCT_NUM_DIMENSIONS) of B
+
+     STRUCT_REF_A and STRUCT_REF_B are the outer references for the
+     latter sequence.  */
+  unsigned int start_a = 0;
+  unsigned int start_b = 0;
+  unsigned int num_dimensions = 0;
+  unsigned int struct_start_a = 0;
+  unsigned int struct_start_b = 0;
+  unsigned int struct_num_dimensions = 0;
+  unsigned int index_a = 0;
+  unsigned int index_b = 0;
+  tree next_ref_a = DR_REF (a);
+  tree next_ref_b = DR_REF (b);
+  tree struct_ref_a = NULL_TREE;
+  tree struct_ref_b = NULL_TREE;
+  while (index_a < num_dimensions_a && index_b < num_dimensions_b)
+    {
+      gcc_checking_assert (handled_component_p (next_ref_a));
+      gcc_checking_assert (handled_component_p (next_ref_b));
+      tree outer_ref_a = TREE_OPERAND (next_ref_a, 0);
+      tree outer_ref_b = TREE_OPERAND (next_ref_b, 0);
+      tree type_a = TREE_TYPE (outer_ref_a);
+      tree type_b = TREE_TYPE (outer_ref_b);
+      if (types_compatible_p (type_a, type_b))
+	{
+	  /* This pair of accesses belong to a suitable sequence.  */
+	  if (start_a + num_dimensions != index_a
+	      || start_b + num_dimensions != index_b)
+	    {
+	      /* Start a new sequence here.  */
+	      start_a = index_a;
+	      start_b = index_b;
+	      num_dimensions = 0;
+	    }
+	  num_dimensions += 1;
+	  if (TREE_CODE (type_a) == RECORD_TYPE)
+	    {
+	      struct_start_a = start_a;
+	      struct_start_b = start_b;
+	      struct_num_dimensions = num_dimensions;
+	      struct_ref_a = outer_ref_a;
+	      struct_ref_b = outer_ref_b;
+	    }
+	  next_ref_a = outer_ref_a;
+	  next_ref_b = outer_ref_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;
+	  next_ref_a = outer_ref_a;
+	}
+      if (size_b <= size_a)
+	{
+	  index_b += 1;
+	  next_ref_b = outer_ref_b;
+	}
     }
 
-  /* 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 the sequence 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 = (start_a + num_dimensions == num_dimensions_a
+		      && start_b + num_dimensions == 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))
+	num_dimensions += 1;
+    }
+  else
+    {
+      start_a = struct_start_a;
+      start_b = struct_start_b;
+      num_dimensions = struct_num_dimensions;
     }
 
-  /* 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 (num_dimensions == 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 (struct_ref_a)
+	  || ref_contains_union_access_p (struct_ref_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 (num_dimensions);
   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 < num_dimensions; ++i)
     {
       struct subscript *subscript;
 
       subscript = XNEW (struct subscript);
+      SUB_ACCESS_FN (subscript, 0) = DR_ACCESS_FN (a, start_a + i);
+      SUB_ACCESS_FN (subscript, 1) = DR_ACCESS_FN (b, 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;
@@ -3163,14 +3312,15 @@ add_outer_distances (struct data_depende
 }
 
 /* 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)
 {
@@ -3188,8 +3338,8 @@ build_classic_dist_vector_1 (struct data
 	  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)
@@ -3249,10 +3399,11 @@ build_classic_dist_vector_1 (struct data
 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;
@@ -3315,10 +3466,11 @@ add_other_self_distances (struct data_de
   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)
 	{
@@ -3330,7 +3482,7 @@ add_other_self_distances (struct data_de
 		  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);
@@ -3401,6 +3553,23 @@ add_distance_for_zero_overlaps (struct d
     }
 }
 
+/* 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.  */
@@ -3432,8 +3601,7 @@ build_classic_dist_vector (struct data_d
     }
 
   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.  */
@@ -3466,12 +3634,11 @@ build_classic_dist_vector (struct data_d
       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;
@@ -3507,12 +3674,10 @@ build_classic_dist_vector (struct data_d
 	    {
 	      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;
 
@@ -3591,13 +3756,13 @@ build_classic_dir_vector (struct data_de
     }
 }
 
-/* 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;
@@ -3609,8 +3774,8 @@ subscript_dependence_tester_1 (struct da
     {
       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);
 
@@ -3659,7 +3824,7 @@ subscript_dependence_tester_1 (struct da
 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);
Index: gcc/tree-ssa-loop-prefetch.c
===================================================================
--- gcc/tree-ssa-loop-prefetch.c	2017-03-28 16:19:28.000000000 +0100
+++ gcc/tree-ssa-loop-prefetch.c	2017-05-03 08:48:48.737038502 +0100
@@ -1650,6 +1650,7 @@ determine_loop_nest_reuse (struct loop *
       refb = (struct mem_ref *) DDR_B (dep)->aux;
 
       if (DDR_ARE_DEPENDENT (dep) == chrec_dont_know
+	  || DDR_COULD_BE_INDEPENDENT_P (dep)
 	  || DDR_NUM_DIST_VECTS (dep) == 0)
 	{
 	  /* If the dependence cannot be analyzed, assume that there might be
Index: gcc/tree-vectorizer.h
===================================================================
--- gcc/tree-vectorizer.h	2017-03-28 16:19:28.000000000 +0100
+++ gcc/tree-vectorizer.h	2017-05-03 08:48:48.738045102 +0100
@@ -383,7 +383,7 @@ #define LOOP_VINFO_ORIG_LOOP_INFO(L)
 #define LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT(L)	\
   ((L)->may_misalign_stmts.length () > 0)
 #define LOOP_REQUIRES_VERSIONING_FOR_ALIAS(L)		\
-  ((L)->may_alias_ddrs.length () > 0)
+  ((L)->comp_alias_ddrs.length () > 0)
 #define LOOP_REQUIRES_VERSIONING_FOR_NITERS(L)		\
   (LOOP_VINFO_NITERS_ASSUMPTIONS (L))
 #define LOOP_REQUIRES_VERSIONING(L)			\
Index: gcc/tree-vect-data-refs.c
===================================================================
--- gcc/tree-vect-data-refs.c	2017-05-03 08:48:30.536704993 +0100
+++ gcc/tree-vect-data-refs.c	2017-05-03 08:48:48.738045102 +0100
@@ -340,6 +340,26 @@ vect_analyze_data_ref_dependence (struct
     }
 
   loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
+
+  if (DDR_COULD_BE_INDEPENDENT_P (ddr))
+    /* For dependence distances of 2 or more, we have the option of
+       limiting VF or checking for an alias at runtime.  Prefer to check
+       at runtime if we can, to avoid limiting the VF unnecessarily when
+       the bases are in fact independent.
+
+       Note that the alias checks will be removed if the VF ends up
+       being small enough.  */
+    FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
+      {
+	int dist = dist_v[loop_depth];
+	if (dist != 0 && !(dist > 0 && DDR_REVERSED_P (ddr)))
+	  {
+	    if (vect_mark_for_runtime_alias_test (ddr, loop_vinfo))
+	      return false;
+	    break;
+	  }
+      }
+
   FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
     {
       int dist = dist_v[loop_depth];
@@ -3017,6 +3037,44 @@ vect_no_alias_p (struct data_reference *
   return false;
 }
 
+/* Return true if the minimum nonzero dependence distance for loop LOOP_DEPTH
+   in DDR is >= VF.  */
+
+static bool
+dependence_distance_ge_vf (data_dependence_relation *ddr,
+			   unsigned int loop_depth, unsigned HOST_WIDE_INT vf)
+{
+  if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE
+      || DDR_NUM_DIST_VECTS (ddr) == 0)
+    return false;
+
+  /* If the dependence is exact, we should have limited the VF instead.  */
+  gcc_checking_assert (DDR_COULD_BE_INDEPENDENT_P (ddr));
+
+  unsigned int i;
+  lambda_vector dist_v;
+  FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
+    {
+      HOST_WIDE_INT dist = dist_v[loop_depth];
+      if (dist != 0
+	  && !(dist > 0 && DDR_REVERSED_P (ddr))
+	  && (unsigned HOST_WIDE_INT) abs_hwi (dist) < vf)
+	return false;
+    }
+
+  if (dump_enabled_p ())
+    {
+      dump_printf_loc (MSG_NOTE, vect_location,
+		       "dependence distance between ");
+      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_A (ddr)));
+      dump_printf (MSG_NOTE,  " and ");
+      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_B (ddr)));
+      dump_printf (MSG_NOTE,  " is >= VF\n");
+    }
+
+  return true;
+}
+
 /* Function vect_prune_runtime_alias_test_list.
 
    Prune a list of ddrs to be tested at run-time by versioning for alias.
@@ -3075,6 +3133,10 @@ vect_prune_runtime_alias_test_list (loop
 
   comp_alias_ddrs.create (may_alias_ddrs.length ());
 
+  unsigned int loop_depth
+    = index_in_loop_nest (LOOP_VINFO_LOOP (loop_vinfo)->num,
+			  LOOP_VINFO_LOOP_NEST (loop_vinfo));
+
   /* First, we collect all data ref pairs for aliasing checks.  */
   FOR_EACH_VEC_ELT (may_alias_ddrs, i, ddr)
     {
@@ -3084,6 +3146,11 @@ vect_prune_runtime_alias_test_list (loop
       tree segment_length_a, segment_length_b;
       gimple *stmt_a, *stmt_b;
 
+      /* Ignore the alias if the VF we chose ended up being no greater
+	 than the dependence distance.  */
+      if (dependence_distance_ge_vf (ddr, loop_depth, vect_factor))
+	continue;
+
       dr_a = DDR_A (ddr);
       stmt_a = DR_STMT (DDR_A (ddr));
       dr_group_first_a = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_a));
@@ -3294,10 +3361,6 @@ vect_prune_runtime_alias_test_list (loop
       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;
 }
 
Index: gcc/testsuite/gcc.dg/vect/vect-alias-check-3.c
===================================================================
--- /dev/null	2017-05-03 08:16:26.972699664 +0100
+++ gcc/testsuite/gcc.dg/vect/vect-alias-check-3.c	2017-05-03 08:48:48.736031902 +0100
@@ -0,0 +1,104 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-additional-options "--param vect-max-version-for-alias-checks=0" } */
+
+/* Intended to be larger than any VF.  */
+#define GAP 128
+#define N (GAP * 3)
+
+struct s { int x[N + 1]; };
+struct t { struct s x[N + 1]; };
+struct u { int x[N + 1]; int y; };
+
+void
+f1 (struct s *a, struct s *b)
+{
+  for (int i = 0; i < N; ++i)
+    a->x[i] += b->x[i];
+}
+
+void
+f2 (struct s *a, struct s *b)
+{
+  for (int i = 0; i < N; ++i)
+    a[1].x[i] += b[2].x[i];
+}
+
+void
+f3 (struct s *a, struct s *b)
+{
+  for (int i = 0; i < N; ++i)
+    a[1].x[i] += b[i].x[i];
+}
+
+void
+f4 (struct s *a, struct s *b)
+{
+  for (int i = 0; i < N; ++i)
+    a[i].x[i] += b[i].x[i];
+}
+
+void
+f5 (struct s *a, struct s *b)
+{
+  for (int i = 0; i < N; ++i)
+    a->x[i] += b->x[i + 1];
+}
+
+void
+f6 (struct s *a, struct s *b)
+{
+  for (int i = 0; i < N; ++i)
+    a[1].x[i] += b[2].x[i + 1];
+}
+
+void
+f7 (struct s *a, struct s *b)
+{
+  for (int i = 0; i < N; ++i)
+    a[1].x[i] += b[i].x[i + 1];
+}
+
+void
+f8 (struct s *a, struct s *b)
+{
+  for (int i = 0; i < N; ++i)
+    a[i].x[i] += b[i].x[i + 1];
+}
+
+void
+f9 (struct s *a, struct t *b)
+{
+  for (int i = 0; i < N; ++i)
+    a->x[i] += b->x[1].x[i];
+}
+
+void
+f10 (struct s *a, struct t *b)
+{
+  for (int i = 0; i < N; ++i)
+    a->x[i] += b->x[i].x[i];
+}
+
+void
+f11 (struct u *a, struct u *b)
+{
+  for (int i = 0; i < N; ++i)
+    a->x[i] += b->x[i] + b[i].y;
+}
+
+void
+f12 (struct s *a, struct s *b)
+{
+  for (int i = 0; i < GAP; ++i)
+    a->x[i + GAP] += b->x[i];
+}
+
+void
+f13 (struct s *a, struct s *b)
+{
+  for (int i = 0; i < GAP * 2; ++i)
+    a->x[i + GAP] += b->x[i];
+}
+
+/* { dg-final { scan-tree-dump-times "LOOP VECTORIZED" 13 "vect" } } */
Index: gcc/testsuite/gcc.dg/vect/vect-alias-check-4.c
===================================================================
--- /dev/null	2017-05-03 08:16:26.972699664 +0100
+++ gcc/testsuite/gcc.dg/vect/vect-alias-check-4.c	2017-05-03 08:48:48.736031902 +0100
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-additional-options "--param vect-max-version-for-alias-checks=0" } */
+
+#define N 16
+
+struct s1 { int a[N]; };
+struct s2 { struct s1 b; int c; };
+struct s3 { int d; struct s1 e; };
+union u { struct s2 f; struct s3 g; };
+
+/* We allow a and b to overlap arbitrarily.  */
+
+void
+f1 (int a[][N], int b[][N])
+{
+  for (int i = 0; i < N; ++i)
+    a[0][i] += b[0][i];
+}
+
+void
+f2 (union u *a, union u *b)
+{
+  for (int i = 0; i < N; ++i)
+    a->f.b.a[i] += b->g.e.a[i];
+}
+
+void
+f3 (struct s1 *a, struct s1 *b)
+{
+  for (int i = 0; i < N - 1; ++i)
+    a->a[i + 1] += b->a[i];
+}
+
+/* { dg-final { scan-tree-dump-not "LOOP VECTORIZED" "vect" } } */
Index: gcc/testsuite/gcc.dg/vect/vect-alias-check-5.c
===================================================================
--- /dev/null	2017-05-03 08:16:26.972699664 +0100
+++ gcc/testsuite/gcc.dg/vect/vect-alias-check-5.c	2017-05-03 08:48:48.736031902 +0100
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+
+/* Intended to be larger than any VF.  */
+#define GAP 128
+#define N (GAP * 3)
+
+struct s { int x[N]; };
+
+void
+f1 (struct s *a, struct s *b)
+{
+  for (int i = 0; i < GAP * 2; ++i)
+    a->x[i + GAP] += b->x[i];
+}
+
+/* { dg-final { scan-tree-dump-times "mark for run-time aliasing" 1 "vect" } } */
+/* { dg-final { scan-tree-dump-times "improved number of alias checks from 1 to 0" 1 "vect" } } */
+/* { dg-final { scan-tree-dump-times "LOOP VECTORIZED" 1 "vect" } } */
