Re: [PATCH 2/2] [graphite] fix invalid bounds on array refs

[Richard Biener <richard.guenther@gmail.com>]

On December 2, 2015 5:34:54 PM GMT+01:00, Sebastian Pop <s.pop@samsung.com> wrote:
>While enabling graphite in -O3 we found a Fortran testcase that fails
>because the max of the type domain is -1.  We used to add that as a
>constraint
>to the elements accessed by the array, leading to a unfeasible
>constraint:
>0 <= i <= -1.  Having that constraint, drops the data reference as that
>says
>that there are no elements accessed in the array.

But either that is the case or the frontend has a bug and should be fixed.  So your patch doesn't make any sense.

Richard.


>---
> gcc/graphite-dependences.c                      | 49 ++++++++++++-
>gcc/graphite-sese-to-poly.c                     | 98
>++++++++++++++-----------
> gcc/testsuite/gfortran.dg/graphite/run-id-3.f90 | 12 +++
> 3 files changed, 114 insertions(+), 45 deletions(-)
> create mode 100644 gcc/testsuite/gfortran.dg/graphite/run-id-3.f90
>
>diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
>index fcc771b..bb81ae3 100644
>--- a/gcc/graphite-dependences.c
>+++ b/gcc/graphite-dependences.c
>@@ -87,7 +87,11 @@ scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
>     {
>       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
> 	if (pdr_read_p (pdr))
>-	  res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
>+	  {
>+	    if (dump_file)
>+	      print_pdr (dump_file, pdr);
>+	    res = isl_union_map_add_map (res, add_pdr_constraints (pdr,
>pbb));
>+	  }
>     }
> 
>   return res;
>@@ -108,7 +112,11 @@ scop_get_must_writes (scop_p scop, vec<poly_bb_p>
>pbbs)
>     {
>       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
> 	if (pdr_write_p (pdr))
>-	  res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
>+	  {
>+	    if (dump_file)
>+	      print_pdr (dump_file, pdr);
>+	    res = isl_union_map_add_map (res, add_pdr_constraints (pdr,
>pbb));
>+	  }
>     }
> 
>   return res;
>@@ -129,7 +137,12 @@ scop_get_may_writes (scop_p scop, vec<poly_bb_p>
>pbbs)
>     {
>       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
> 	if (pdr_may_write_p (pdr))
>-	  res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
>+	  {
>+	    if (dump_file)
>+	      print_pdr (dump_file, pdr);
>+
>+	    res = isl_union_map_add_map (res, add_pdr_constraints (pdr,
>pbb));
>+	  }
>     }
> 
>   return res;
>@@ -313,6 +326,36 @@ compute_deps (scop_p scop, vec<poly_bb_p> pbbs,
>   isl_union_map *empty = isl_union_map_empty (space);
>   isl_union_map *original = scop_get_original_schedule (scop, pbbs);
> 
>+  if (dump_file)
>+    {
>+      fprintf (dump_file, "\n--- Documentation for datarefs dump:
>---\n");
>+      fprintf (dump_file, "Statements on the iteration domain are
>mapped to"
>+	       " array references.\n");
>+      fprintf (dump_file, "  To read the following data
>references:\n\n");
>+      fprintf (dump_file, "  S_5[i0] -> [106] : i0 >= 0 and i0 <=
>3\n");
>+      fprintf (dump_file, "  S_8[i0] -> [1, i0] : i0 >= 0 and i0 <=
>3\n\n");
>+
>+      fprintf (dump_file, "  S_5[i0] is the dynamic instance of
>statement"
>+	       " bb_5 in a loop that accesses all iterations 0 <= i0 <=
>3.\n");
>+      fprintf (dump_file, "  [1, i0] is a 'memref' with alias set 1"
>+	       " and first subscript access i0.\n");
>+      fprintf (dump_file, "  [106] is a 'scalar reference' which is
>the sum of"
>+	       " SSA_NAME_VERSION 6"
>+	       " and --param graphite-max-arrays-per-scop=100\n");
>+      fprintf (dump_file, "-----------------------\n\n");
>+
>+      fprintf (dump_file, "data references (\n");
>+      fprintf (dump_file, "  reads: ");
>+      print_isl_union_map (dump_file, reads);
>+      fprintf (dump_file, "  must_writes: ");
>+      print_isl_union_map (dump_file, must_writes);
>+      fprintf (dump_file, "  may_writes: ");
>+      print_isl_union_map (dump_file, may_writes);
>+      fprintf (dump_file, "  all_writes: ");
>+      print_isl_union_map (dump_file, all_writes);
>+      fprintf (dump_file, ")\n");
>+    }
>+
>   isl_union_map_compute_flow (isl_union_map_copy (reads),
> 			      isl_union_map_copy (must_writes),
> 			      isl_union_map_copy (may_writes),
>diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
>index 7ef01fb..887c212 100644
>--- a/gcc/graphite-sese-to-poly.c
>+++ b/gcc/graphite-sese-to-poly.c
>@@ -922,6 +922,33 @@ pdr_add_memory_accesses (isl_map *acc, dr_info
>&dri)
>   return acc;
> }
> 
>+/* Return true when the LOW and HIGH bounds of an array reference REF
>are valid
>+   to extract constraints on accessed elements of the array. 
>Returning false is
>+   the conservative answer.  */
>+
>+static bool
>+bounds_are_valid (tree ref, tree low, tree high)
>+{
>+  if (!high)
>+    return false;
>+
>+  if (!tree_fits_shwi_p (low)
>+      || !tree_fits_shwi_p (high))
>+    return false;
>+
>+  /* 1-element arrays at end of structures may extend over
>+     their declared size.  */
>+  if (array_at_struct_end_p (ref)
>+      && operand_equal_p (low, high, 0))
>+    return false;
>+
>+  /* Fortran has some arrays where high bound is -1 and low is 0.  */
>+  if (integer_onep (fold_build2 (LT_EXPR, boolean_type_node, high,
>low)))
>+    return false;
>+
>+  return true;
>+}
>+
> /* Add constrains representing the size of the accessed data to the
>    ACCESSES polyhedron.  ACCESSP_NB_DIMS is the dimension of the
>    ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
>@@ -942,48 +969,35 @@ pdr_add_data_dimensions (isl_set
>*subscript_sizes, scop_p scop,
>       tree low = array_ref_low_bound (ref);
>       tree high = array_ref_up_bound (ref);
> 
>-      /* XXX The PPL code dealt separately with
>-         subscript - low >= 0 and high - subscript >= 0 in case one of
>-	 the two bounds isn't known.  Do the same here?  */
>-
>-      if (tree_fits_shwi_p (low)
>-	  && high
>-	  && tree_fits_shwi_p (high)
>-	  /* 1-element arrays at end of structures may extend over
>-	     their declared size.  */
>-	  && !(array_at_struct_end_p (ref)
>-	       && operand_equal_p (low, high, 0)))
>-	{
>-	  isl_id *id;
>-	  isl_aff *aff;
>-	  isl_set *univ, *lbs, *ubs;
>-	  isl_pw_aff *index;
>-	  isl_set *valid;
>-	  isl_space *space = isl_set_get_space (subscript_sizes);
>-	  isl_pw_aff *lb = extract_affine_int (low, isl_space_copy (space));
>-	  isl_pw_aff *ub = extract_affine_int (high, isl_space_copy (space));
>-
>-	  /* high >= 0 */
>-	  valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub));
>-	  valid = isl_set_project_out (valid, isl_dim_set, 0,
>-				       isl_set_dim (valid, isl_dim_set));
>-	  scop->param_context = isl_set_intersect (scop->param_context,
>valid);
>-
>-	  aff = isl_aff_zero_on_domain (isl_local_space_from_space (space));
>-	  aff = isl_aff_add_coefficient_si (aff, isl_dim_in, i + 1, 1);
>-	  univ = isl_set_universe (isl_space_domain (isl_aff_get_space
>(aff)));
>-	  index = isl_pw_aff_alloc (univ, aff);
>-
>-	  id = isl_set_get_tuple_id (subscript_sizes);
>-	  lb = isl_pw_aff_set_tuple_id (lb, isl_dim_in, isl_id_copy (id));
>-	  ub = isl_pw_aff_set_tuple_id (ub, isl_dim_in, id);
>-
>-	  /* low <= sub_i <= high */
>-	  lbs = isl_pw_aff_ge_set (isl_pw_aff_copy (index), lb);
>-	  ubs = isl_pw_aff_le_set (index, ub);
>-	  subscript_sizes = isl_set_intersect (subscript_sizes, lbs);
>-	  subscript_sizes = isl_set_intersect (subscript_sizes, ubs);
>-	}
>+      if (!bounds_are_valid (ref, low, high))
>+	continue;
>+
>+      isl_space *space = isl_set_get_space (subscript_sizes);
>+      isl_pw_aff *lb = extract_affine_int (low, isl_space_copy
>(space));
>+      isl_pw_aff *ub = extract_affine_int (high, isl_space_copy
>(space));
>+
>+      /* high >= 0 */
>+      isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub));
>+      valid = isl_set_project_out (valid, isl_dim_set, 0,
>+				   isl_set_dim (valid, isl_dim_set));
>+      scop->param_context = isl_set_intersect (scop->param_context,
>valid);
>+
>+      isl_aff *aff
>+	= isl_aff_zero_on_domain (isl_local_space_from_space (space));
>+      aff = isl_aff_add_coefficient_si (aff, isl_dim_in, i + 1, 1);
>+      isl_set *univ
>+	= isl_set_universe (isl_space_domain (isl_aff_get_space (aff)));
>+      isl_pw_aff *index = isl_pw_aff_alloc (univ, aff);
>+
>+      isl_id *id = isl_set_get_tuple_id (subscript_sizes);
>+      lb = isl_pw_aff_set_tuple_id (lb, isl_dim_in, isl_id_copy (id));
>+      ub = isl_pw_aff_set_tuple_id (ub, isl_dim_in, id);
>+
>+      /* low <= sub_i <= high */
>+      isl_set *lbs = isl_pw_aff_ge_set (isl_pw_aff_copy (index), lb);
>+      isl_set *ubs = isl_pw_aff_le_set (index, ub);
>+      subscript_sizes = isl_set_intersect (subscript_sizes, lbs);
>+      subscript_sizes = isl_set_intersect (subscript_sizes, ubs);
>     }
> 
>   return subscript_sizes;
>diff --git a/gcc/testsuite/gfortran.dg/graphite/run-id-3.f90
>b/gcc/testsuite/gfortran.dg/graphite/run-id-3.f90
>new file mode 100644
>index 0000000..54139ef
>--- /dev/null
>+++ b/gcc/testsuite/gfortran.dg/graphite/run-id-3.f90
>@@ -0,0 +1,12 @@
>+! { dg-do run }
>+! { dg-options "-ffrontend-optimize -floop-nest-optimize" }
>+! PR 56872 - wrong front-end optimization with a single constructor.
>+! Original bug report by Rich Townsend.
>+  integer :: k
>+  real :: s
>+  integer :: m
>+  s = 2.0
>+  m = 4
>+  res = SUM([(s**(REAL(k-1)/REAL(m-1)),k=1,m)])
>+  if (abs(res - 5.84732246) > 1e-6) call abort
>+  end