Re: [PATCH][GRAPHITE] Allow --param graphite-max-arrays-per-scop=0

[Richard Biener]

On Thu, 28 Sep 2017, Sebastian Pop wrote:

> On Wed, Sep 27, 2017 at 6:51 AM, Richard Biener  wrote:
> >
> > The following is to allow making --param graphite-max-arrays-per-scop
> > unbounded.  That's a little tricky because the bound is used when
> > computing "alias-sets" for scalar constraints.  There's an easy way
> > out though as we know the maximum alias-set assigned in the SCOP,
> > we only have to remember it.  The advantage (if it matters at all)
> > is that we avoid a constraint coefficient gap between that last
> > used alias-set and the former PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP.
> >
> > Bootstrap and regtest running on x86_64-unknown-linux-gnu, SPEC CPU 2006
> > tested.  Will apply after testing finished.
> >
> > Richard.
> >
> > 2017-09-27  Richard Biener  
> >
> > * graphite.h (scop::max_alias_set): New member.
> > * graphite-scop-detection.c: Remove references to non-existing
> > --param in comments.
> > (build_alias_sets): Record the maximum alias set used for drs.
> > (build_scops): Support zero as unlimited for
> > --param graphite-max-arrays-per-scop.
> > * graphite-sese-to-poly.c (add_scalar_version_numbers): Remove
> > and inline into ...
> > (build_poly_sr_1): ... here.  Compute alias set based on the
> > maximum alias set used for drs rather than
> > PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
> >
> 
> Maybe we should keep this limit, and instead of failing to handle
> huge scops, we could stop the scop detection to expand the
> scop past this limit?

Yes, I believe we should put all the checks we do to discard SCOPs
at SESE region build time and try if smaller regions would fit within
the limits.

Of course it's hard to guess whether ISL will eventually time-out or 
not...

Another check that kills quite many SCOPs in the end is verifying
whether we can handle the dependences - unfortunately that one is
necessarily quadratic in the number of DRs... (hacking this away
as in if we'd do versioning on a proper condition gets us 10 times
more SCOPs in SPEC CPU 2006 but only 50 more transforms because
code-gen errors sky-rocket).

I'm going to leave the limits in place right now as I'm shifting
towards fixing existing code-gen issues at the moment.

Richard.

Re: [PATCH][GRAPHITE] Allow --param graphite-max-arrays-per-scop=0

[Sebastian Pop]

On Wed, Sep 27, 2017 at 6:51 AM, Richard Biener  wrote:
>
> The following is to allow making --param graphite-max-arrays-per-scop
> unbounded.  That's a little tricky because the bound is used when
> computing "alias-sets" for scalar constraints.  There's an easy way
> out though as we know the maximum alias-set assigned in the SCOP,
> we only have to remember it.  The advantage (if it matters at all)
> is that we avoid a constraint coefficient gap between that last
> used alias-set and the former PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP.
>
> Bootstrap and regtest running on x86_64-unknown-linux-gnu, SPEC CPU 2006
> tested.  Will apply after testing finished.
>
> Richard.
>
> 2017-09-27  Richard Biener  
>
> * graphite.h (scop::max_alias_set): New member.
> * graphite-scop-detection.c: Remove references to non-existing
> --param in comments.
> (build_alias_sets): Record the maximum alias set used for drs.
> (build_scops): Support zero as unlimited for
> --param graphite-max-arrays-per-scop.
> * graphite-sese-to-poly.c (add_scalar_version_numbers): Remove
> and inline into ...
> (build_poly_sr_1): ... here.  Compute alias set based on the
> maximum alias set used for drs rather than
> PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
>

Maybe we should keep this limit, and instead of failing to handle
huge scops, we could stop the scop detection to expand the
scop past this limit?

[PATCH][GRAPHITE] Allow --param graphite-max-arrays-per-scop=0

[Richard Biener]

The following is to allow making --param graphite-max-arrays-per-scop
unbounded.  That's a little tricky because the bound is used when
computing "alias-sets" for scalar constraints.  There's an easy way
out though as we know the maximum alias-set assigned in the SCOP,
we only have to remember it.  The advantage (if it matters at all)
is that we avoid a constraint coefficient gap between that last
used alias-set and the former PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP.

Bootstrap and regtest running on x86_64-unknown-linux-gnu, SPEC CPU 2006
tested.  Will apply after testing finished.

Richard.

2017-09-27  Richard Biener  

* graphite.h (scop::max_alias_set): New member.
* graphite-scop-detection.c: Remove references to non-existing
--param in comments.
(build_alias_sets): Record the maximum alias set used for drs.
(build_scops): Support zero as unlimited for
--param graphite-max-arrays-per-scop.
* graphite-sese-to-poly.c (add_scalar_version_numbers): Remove
and inline into ...
(build_poly_sr_1): ... here.  Compute alias set based on the
maximum alias set used for drs rather than
PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP

Index: gcc/graphite-scop-detection.c
===
--- gcc/graphite-scop-detection.c   (revision 253226)
+++ gcc/graphite-scop-detection.c   (working copy)
@@ -389,10 +389,7 @@ public:
 
   void remove_intersecting_scops (sese_l s1);
 
-  /* Return true when a statement in SCOP cannot be represented by Graphite.
- The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
- Limit the number of bbs between adjacent loops to
- PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS.  */
+  /* Return true when a statement in SCOP cannot be represented by Graphite.  
*/
 
   bool harmful_loop_in_region (sese_l scop) const;
 
@@ -760,10 +757,7 @@ scop_detection::add_scop (sese_l s)
   DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, 
s));
 }
 
-/* Return true when a statement in SCOP cannot be represented by Graphite.
-   The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
-   Limit the number of bbs between adjacent loops to
-   PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS.  */
+/* Return true when a statement in SCOP cannot be represented by Graphite.  */
 
 bool
 scop_detection::harmful_loop_in_region (sese_l scop) const
@@ -1531,7 +1525,8 @@ build_alias_set (scop_p scop)
   for (i = 0; i < num_vertices; i++)
 all_vertices[i] = i;
 
-  graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL);
+  scop->max_alias_set
+= graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
   free (all_vertices);
 
   for (i = 0; i < g->n_vertices; i++)
@@ -1755,7 +1750,8 @@ build_scops (vec *scops)
}
 
   unsigned max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP);
-  if (scop->drs.length () >= max_arrays)
+  if (max_arrays > 0
+ && scop->drs.length () >= max_arrays)
{
  DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
   << scop->drs.length ()
Index: gcc/graphite-sese-to-poly.c
===
--- gcc/graphite-sese-to-poly.c (revision 253225)
+++ gcc/graphite-sese-to-poly.c (working copy)
@@ -491,25 +491,6 @@ pdr_add_alias_set (isl_map *acc, dr_info
   return isl_map_add_constraint (acc, c);
 }
 
-/* Add a constrain to the ACCESSES polyhedron for the alias set of
-   data reference DR.  ACCESSP_NB_DIMS is the dimension of the
-   ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
-   domain.  */
-
-static isl_map *
-add_scalar_version_numbers (isl_map *acc, tree var)
-{
-  isl_constraint *c = isl_equality_alloc
-  (isl_local_space_from_space (isl_map_get_space (acc)));
-  int max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP);
-  /* Each scalar variables has a unique alias set number starting from
- max_arrays.  */
-  c = isl_constraint_set_constant_si (c, -max_arrays - SSA_NAME_VERSION (var));
-  c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1);
-
-  return isl_map_add_constraint (acc, c);
-}
-
 /* Assign the affine expression INDEX to the output dimension POS of
MAP and return the result.  */
 
@@ -684,13 +665,21 @@ static void
 build_poly_sr_1 (poly_bb_p pbb, gimple *stmt, tree var, enum poly_dr_type kind,
 isl_map *acc, isl_set *subscript_sizes)
 {
-  int max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP);
+  scop_p scop = PBB_SCOP (pbb);
   /* Each scalar variables has a unique alias set number starting from
- max_arrays.  */
+ the maximum alias set assigned to a dr.  */
+  int alias_set = scop->max_alias_set + SSA_NAME_VERSION (var);
   subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0,
-