Patchwork [2/4] Conservatively estimate subscript upper bound from the loop iteration domain.

login
register
mail settings
Submitter Sebastian Pop
Date Dec. 25, 2010, 6:26 a.m.
Message ID <1293258413-29902-3-git-send-email-sebpop@gmail.com>
Download mbox | patch
Permalink /patch/76662/
State New
Headers show

Comments

Sebastian Pop - Dec. 25, 2010, 6:26 a.m.
2010-12-25  Alexander Monakov  <amonakov@ispras.ru>

	* graphite-dependences.c (graphite_outer_subscript_bound): New.
	(graphite_carried_dependence_level_k): Export.
	* graphite-dependences.h (graphite_outer_subscript_bound): Declare.
	(graphite_carried_dependence_level_k): Ditto.
---
 gcc/ChangeLog.graphite     |    7 +++
 gcc/graphite-dependences.c |  130 +++++++++++++++++++++++++++++++++++++++++++-
 gcc/graphite-dependences.h |    3 +
 3 files changed, 139 insertions(+), 1 deletions(-)

Patch

diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 9d03354..d667086 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,3 +1,10 @@ 
+2010-12-25  Alexander Monakov  <amonakov@ispras.ru>
+
+	* graphite-dependences.c (graphite_outer_subscript_bound): New.
+	(graphite_carried_dependence_level_k): Export.
+	* graphite-dependences.h (graphite_outer_subscript_bound): Declare.
+	(graphite_carried_dependence_level_k): Ditto.
+
 2010-12-25  Alexey Kravets  <kayrick@ispras.ru>
 
 	* graphite-clast-to-gimple.c (struct clast_name_index): Move
diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index 3986de4..6eeaf60 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -47,6 +47,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "graphite.h"
 #include "graphite-poly.h"
 #include "graphite-dependences.h"
+#include "graphite-cloog-util.h"
 
 /* Returns a new polyhedral Data Dependence Relation (DDR).  SOURCE is
    the source data reference, SINK is the sink data reference.  When
@@ -752,10 +753,137 @@  graphite_legal_transform (scop_p scop)
   return true;
 }
 
+/* Return a tree with upper bound on PDR's outermost index (if PDR's outermost
+   type is INDIRECT_REF), or NULL if the bound could not be found.  */
+
+tree
+graphite_outer_subscript_bound (poly_dr_p pdr,
+				bool minmax ATTRIBUTE_UNUSED)
+{
+  tree bound_tree = NULL_TREE;
+  poly_bb_p pbb = PDR_PBB (pdr);
+  graphite_dim_t tdim = pbb_nb_scattering_transform (pbb);
+  graphite_dim_t ddim = pbb_dim_iter_domain (pbb);
+
+  graphite_dim_t sdim = PDR_NB_SUBSCRIPTS (pdr) + 1;
+  graphite_dim_t dim1 = pdr_dim (pdr);
+
+  scop_p scop = PBB_SCOP (pbb);
+  graphite_dim_t gdim = scop_nb_params (scop);
+
+  graphite_dim_t dim = tdim + dim1;
+
+  ppl_Pointset_Powerset_C_Polyhedron_t isc, idr, res;
+
+  combine_context_id_scat (&isc, pbb, false);
+  ppl_insert_dimensions_pointset (isc, tdim + ddim, sdim);
+  idr = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr), ddim, ddim + gdim,
+			      tdim, 0);
+
+  ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0);
+  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, isc);
+  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr);
+
+  ppl_delete_Pointset_Powerset_C_Polyhedron (isc);
+  ppl_delete_Pointset_Powerset_C_Polyhedron (idr);
+
+  {
+    ppl_Linear_Expression_t le;
+    ppl_Coefficient_t coef;
+    mpz_t v;
+    unsigned i;
+
+    mpz_init (v);
+    mpz_set_si (v, 1);
+    ppl_new_Coefficient (&coef);
+    ppl_assign_Coefficient_from_mpz_t (coef, v);
+
+    ppl_new_Linear_Expression_with_dimension (&le, dim);
+
+    for (i = 0; i < dim - sdim + 1 - gdim; i++)
+      ppl_Pointset_Powerset_C_Polyhedron_affine_image (res, i, le, coef);
+  }
+
+  {
+    ppl_dimension_type *ds = XNEWVEC (ppl_dimension_type, dim - gdim - 1);
+    unsigned i, pos, sub1_dim = dim - sdim + 1 - gdim;
+    for (i = 0, pos = 0; i < dim - gdim; i++)
+      if (i != sub1_dim)
+	ds[pos++] = i;
+
+    ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (res, ds,
+								dim
+								- gdim
+								- 1);
+    XDELETEVEC (ds);
+  }
+
+  {
+    ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
+    ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
+    ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
+
+    for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (res, it),
+	   ppl_Pointset_Powerset_C_Polyhedron_iterator_end (res, end);
+	 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
+	 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
+      {
+	ppl_const_Polyhedron_t ph;
+	CloogMatrix *mat;
+	int i;
+	unsigned j;
+
+	ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
+	mat = new_Cloog_Matrix_from_ppl_Polyhedron (ph);
+
+	for (i = 0; i < (int) mat->NbRows; i++)
+	  if (mpz_cmp_si (mat->p[i][0], 0) == 0
+	      && mpz_cmp_si (mat->p[i][1], 0) != 0)
+	    {
+	      bound_tree = size_zero_node;
+	      break;
+	    }
+	  else if (mpz_cmp_si (mat->p[i][0], 1) == 0
+		   && mpz_cmp_si (mat->p[i][1], 0) < 0)
+	    {
+	      tree dt = gmp_cst_to_tree (sizetype, mat->p[i][1]);
+	      tree t = gmp_cst_to_tree (sizetype, mat->p[i][gdim+2]);
+
+	      for (j = 0; j < gdim; j++)
+		{
+		  tree p, vt = gmp_cst_to_tree (sizetype, mat->p[i][j+2]);
+
+		  p = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), j);
+		  p = fold_convert (sizetype, p);
+		  p = fold_build2 (MULT_EXPR, sizetype, vt, p);
+		  t = fold_build2 (PLUS_EXPR, sizetype, t, p);
+		}
+
+	      dt = fold_build1 (NEGATE_EXPR, sizetype, dt);
+	      t = fold_build2 (FLOOR_DIV_EXPR, sizetype, t, dt);
+
+	      if (!bound_tree)
+		bound_tree = t;
+	      else
+		bound_tree = fold_build2 (MIN_EXPR, sizetype,
+					  bound_tree, t);
+	    }
+
+	cloog_matrix_free (mat);
+      }
+
+    ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
+    ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
+  }
+
+  ppl_delete_Pointset_Powerset_C_Polyhedron (res);
+  return bound_tree;
+}
+
 /* Returns TRUE when the dependence polyhedron between PDR1 and
    PDR2 represents a loop carried dependence at level LEVEL.  */
 
-static bool
+bool
 graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
 				     int level)
 {
diff --git a/gcc/graphite-dependences.h b/gcc/graphite-dependences.h
index f6f4fea..01196b2 100644
--- a/gcc/graphite-dependences.h
+++ b/gcc/graphite-dependences.h
@@ -24,6 +24,8 @@  along with GCC; see the file COPYING3.  If not see
 extern bool graphite_legal_transform (scop_p);
 extern bool dependency_between_pbbs_p (poly_bb_p, poly_bb_p, int);
 
+extern bool graphite_carried_dependence_level_k (poly_dr_p, poly_dr_p, int);
+
 enum poly_dependence_kind {
   unknown_dependence,
   no_dependence,
@@ -58,6 +60,7 @@  extern hashval_t hash_poly_ddr_p (const void *);
 extern void free_poly_ddr (void *);
 extern void dot_deps (scop_p);
 extern void dot_deps_stmt (scop_p);
+extern tree graphite_outer_subscript_bound (poly_dr_p, bool);
 extern void print_pddr (FILE *, poly_ddr_p);
 extern void debug_pddr (poly_ddr_p);