Patchwork [12/20] add pbb->domain

login
register
mail settings
Submitter Sebastian Pop
Date Aug. 15, 2011, 7:12 a.m.
Message ID <1313392379-1525-12-git-send-email-sebpop@gmail.com>
Download mbox | patch
Permalink /patch/110003/
State New
Headers show

Comments

Sebastian Pop - Aug. 15, 2011, 7:12 a.m.
---
 gcc/graphite-poly.c         |   12 +++-
 gcc/graphite-poly.h         |    6 ++
 gcc/graphite-sese-to-poly.c |  205 +++++++++++++++++++++++++++++++++++--------
 3 files changed, 187 insertions(+), 36 deletions(-)

Patch

diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c
index fd2703b..ce0649b 100644
--- a/gcc/graphite-poly.c
+++ b/gcc/graphite-poly.c
@@ -880,6 +880,7 @@  new_poly_bb (scop_p scop, void *black_box)
   poly_bb_p pbb = XNEW (struct poly_bb);
 
   PBB_DOMAIN (pbb) = NULL;
+  pbb->domain = NULL;
   PBB_SCOP (pbb) = scop;
   pbb_set_black_box (pbb, black_box);
   PBB_TRANSFORMED (pbb) = NULL;
@@ -901,7 +902,10 @@  free_poly_bb (poly_bb_p pbb)
   int i;
   poly_dr_p pdr;
 
-  ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb));
+  if (PBB_DOMAIN (pbb))
+    ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb));
+
+  isl_set_free (pbb->domain);
 
   if (PBB_TRANSFORMED (pbb))
     poly_scattering_free (PBB_TRANSFORMED (pbb));
@@ -1096,6 +1100,12 @@  print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
   graphite_dim_t i;
   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
 
+  {
+    isl_printer *pp = isl_printer_to_file (PBB_SCOP (pbb)->ctx, file);
+    pp = isl_printer_print_set (pp, pbb->domain);
+    isl_printer_free (pp);
+  }
+
   if (!PBB_DOMAIN (pbb))
     return;
 
diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h
index bb8771d..3483ef0 100644
--- a/gcc/graphite-poly.h
+++ b/gcc/graphite-poly.h
@@ -502,6 +502,12 @@  pbb_dim_iter_domain (const struct poly_bb *pbb)
 {
   scop_p scop = PBB_SCOP (pbb);
   ppl_dimension_type dim;
+  isl_dim *d = isl_set_get_dim (pbb->domain);
+  graphite_dim_t res = isl_dim_size (d, isl_dim_set);
+
+  isl_dim_free (d);
+  if (0)
+    return res;
 
   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim);
   return dim - scop_nb_params (scop);
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 9723427..20bcf1f 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -658,20 +658,6 @@  isl_id_for_ssa_name (scop_p s, tree e)
   return id;
 }
 
-/* Return an ISL identifier from the loop L.  */
-
-static isl_id *
-isl_id_for_loop (scop_p s, loop_p l)
-{
-  isl_id *id;
-  char name[50];
-
-  snprintf (name, sizeof (name), "L_%d", l ? l->num : -1);
-  id = isl_id_alloc (s->ctx, name, l);
-
-  return id;
-}
-
 /* Extract an affine expression from the ssa_name E.  */
 
 static isl_pw_aff *
@@ -1182,10 +1168,6 @@  find_scop_parameters (scop_p scop)
       dim = isl_dim_set_dim_id (dim, isl_dim_param, i,
 				isl_id_for_ssa_name (scop, e));
 
-    for (i = 0; i < nbl; i++)
-      dim = isl_dim_set_dim_id (dim, isl_dim_set, i,
-				isl_id_for_loop (scop, get_loop (i)));
-
     scop->context = isl_set_universe (dim);
   }
 }
@@ -1263,7 +1245,8 @@  add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit,
 static void
 build_loop_iteration_domains (scop_p scop, struct loop *loop,
                               ppl_Polyhedron_t outer_ph, int nb,
-			      ppl_Pointset_Powerset_C_Polyhedron_t *domains)
+			      ppl_Pointset_Powerset_C_Polyhedron_t *domains,
+			      isl_set *outer, isl_set **doms)
 {
   int i;
   ppl_Polyhedron_t ph;
@@ -1271,6 +1254,15 @@  build_loop_iteration_domains (scop_p scop, struct loop *loop,
   ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
   sese region = SCOP_REGION (scop);
 
+  isl_set *inner = isl_set_copy (outer);
+  isl_dim *dimension = isl_set_get_dim (scop->context);
+  int pos = loop->num;
+  isl_int v;
+  mpz_t g;
+
+  mpz_init (g);
+  isl_int_init (v);
+
   {
     ppl_const_Constraint_System_t pcs;
     ppl_dimension_type *map
@@ -1301,8 +1293,16 @@  build_loop_iteration_domains (scop_p scop, struct loop *loop,
     ppl_delete_Linear_Expression (lb_expr);
     ppl_Polyhedron_add_constraint (ph, lb);
     ppl_delete_Constraint (lb);
+
+    {
+      isl_constraint *c = isl_inequality_alloc (isl_dim_copy (dimension));
+
+      c = isl_constraint_set_coefficient_si (c, isl_dim_set, pos, 1);
+      inner = isl_set_add_constraint (inner, c);
+    }
   }
 
+  /* loop_i <= cst_nb_iters */
   if (TREE_CODE (nb_iters) == INTEGER_CST)
     {
       ppl_Constraint_t ub;
@@ -1310,14 +1310,25 @@  build_loop_iteration_domains (scop_p scop, struct loop *loop,
 
       ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
 
-      /* loop_i <= cst_nb_iters */
       ppl_set_coef (ub_expr, nb, -1);
       ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
       ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
       ppl_Polyhedron_add_constraint (ph, ub);
       ppl_delete_Linear_Expression (ub_expr);
       ppl_delete_Constraint (ub);
+
+      {
+	isl_constraint *c = isl_inequality_alloc (isl_dim_copy (dimension));
+
+	c = isl_constraint_set_coefficient_si (c, isl_dim_set, pos, -1);
+	tree_int_to_gmp (nb_iters, g);
+	isl_int_set_gmp (v, g);
+	c = isl_constraint_set_constant (c, v);
+	inner = isl_set_add_constraint (inner, c);
+      }
     }
+
+  /* loop_i <= expr_nb_iters */
   else if (!chrec_contains_undetermined (nb_iters))
     {
       mpz_t one;
@@ -1337,6 +1348,15 @@  build_loop_iteration_domains (scop_p scop, struct loop *loop,
       scop->context = isl_set_intersect
 	(scop->context, isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff)));
 
+      {
+	isl_local_space *ls = isl_local_space_from_dim (isl_dim_copy (dimension));
+	isl_aff *al = isl_aff_set_coefficient_si
+	  (isl_aff_zero (ls), isl_dim_set, pos, 1);
+	isl_set *le = isl_pw_aff_le_set (isl_pw_aff_from_aff (al),
+					 isl_pw_aff_copy (aff));
+	inner = isl_set_intersect (inner, le);
+      }
+
       if (max_stmt_executions (loop, true, &nit))
 	{
 	  add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr);
@@ -1361,7 +1381,6 @@  build_loop_iteration_domains (scop_p scop, struct loop *loop,
 	  }
 	}
 
-      /* loop_i <= expr_nb_iters */
       ppl_set_coef (ub_expr, nb, -1);
       ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
       ppl_Polyhedron_add_constraint (ph, ub);
@@ -1372,17 +1391,51 @@  build_loop_iteration_domains (scop_p scop, struct loop *loop,
     gcc_unreachable ();
 
   if (loop->inner && loop_in_sese_p (loop->inner, region))
-    build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
+    build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains,
+				  isl_set_copy (inner), doms);
 
   if (nb != 0
       && loop->next
       && loop_in_sese_p (loop->next, region))
-    build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
+    build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains,
+				  isl_set_copy (outer), doms);
 
   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
     (&domains[loop->num], ph);
-
   ppl_delete_Polyhedron (ph);
+
+
+  {
+    isl_dim *dc = isl_set_get_dim (scop->context);
+    int nb_out = isl_dim_size (dc, isl_dim_set);
+    isl_dim *dim = isl_dim_add (isl_dim_from_domain (dc), isl_dim_out,
+				nb_out);
+    isl_map *map = isl_map_identity (dim);
+    loop_p outer;
+
+    /* Set all the loops that are not part of the current loop nest to
+       0.  This includes the outermost loop (i.e., loop_0 is the body
+       of the function).  This is needed for the data dependence
+       analysis to work, as otherwise all these dimensions would not
+       be bounded.  */
+    for (i = 0; i < nb_out; i++)
+      if (i == 0
+	  || !(outer = get_loop (i))
+	  || (loop != outer
+	      && !flow_loop_nested_p (outer, loop)))
+	{
+	  isl_constraint *c = isl_equality_alloc (isl_map_get_dim (map));
+	  c = isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1);
+	  map = isl_map_add_constraint (map, c);
+	}
+
+    doms[loop->num] = isl_set_apply (inner, map);
+  }
+
+  isl_set_free (outer);
+  isl_dim_free (dimension);
+  isl_int_clear (v);
+  mpz_clear (g);
 }
 
 /* Returns a linear expression for tree T evaluated in PBB.  */
@@ -1494,6 +1547,19 @@  add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
   ppl_delete_Linear_Expression (right);
 }
 
+/* Returns a linear expression for tree T evaluated in PBB.  */
+
+static isl_pw_aff *
+create_pw_aff_from_tree (poly_bb_p pbb, tree t)
+{
+  scop_p scop = PBB_SCOP (pbb);
+
+  t = scalar_evolution_in_region (SCOP_REGION (scop), pbb_loop (pbb), t);
+  gcc_assert (!automatically_generated_chrec_p (t));
+
+  return extract_affine (scop, t);
+}
+
 /* Add conditional statement STMT to pbb.  CODE is used as the comparision
    operator.  This allows us to invert the condition or to handle
    inequalities.  */
@@ -1514,6 +1580,48 @@  add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
     }
   else
     add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
+
+  {
+    isl_pw_aff *lhs = create_pw_aff_from_tree (pbb, gimple_cond_lhs (stmt));
+    isl_pw_aff *rhs = create_pw_aff_from_tree (pbb, gimple_cond_rhs (stmt));
+    isl_set *cond;
+
+    switch (code)
+      {
+      case LT_EXPR:
+	cond = isl_pw_aff_lt_set (lhs, rhs);
+	break;
+
+      case GT_EXPR:
+	cond = isl_pw_aff_gt_set (lhs, rhs);
+	break;
+
+      case LE_EXPR:
+	cond = isl_pw_aff_le_set (lhs, rhs);
+	break;
+
+      case GE_EXPR:
+	cond = isl_pw_aff_ge_set (lhs, rhs);
+	break;
+
+      case EQ_EXPR:
+	cond = isl_pw_aff_eq_set (lhs, rhs);
+	break;
+
+      case NE_EXPR:
+	cond = isl_pw_aff_ne_set (lhs, rhs);
+	break;
+
+      default:
+	isl_pw_aff_free(lhs);
+	isl_pw_aff_free(rhs);
+	return;
+      }
+
+    cond = isl_set_coalesce (cond);
+    cond = isl_set_set_tuple_id (cond, isl_set_get_tuple_id (pbb->domain));
+    pbb->domain = isl_set_intersect (pbb->domain, cond);
+  }
 }
 
 /* Add conditions to the domain of PBB.  */
@@ -1810,31 +1918,56 @@  build_scop_iteration_domain (scop_p scop)
   int nb_loops = number_of_loops ();
   ppl_Pointset_Powerset_C_Polyhedron_t *domains
     = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
+  isl_set **doms = XNEWVEC (isl_set *, nb_loops);
 
   for (i = 0; i < nb_loops; i++)
-    domains[i] = NULL;
+    {
+      domains[i] = NULL;
+      doms[i] = NULL;
+    }
 
   ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
 
   FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
     if (!loop_in_sese_p (loop_outer (loop), region))
-      build_loop_iteration_domains (scop, loop, ph, 0, domains);
+      build_loop_iteration_domains (scop, loop, ph, 0, domains,
+				    isl_set_copy (scop->context), doms);
 
   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
-    if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
-      ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
-	(&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
-	 domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
-    else
-      ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
-	(&PBB_DOMAIN (pbb), ph);
+    {
+      loop = pbb_loop (pbb);
+
+      if (domains[loop->num])
+      	ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
+	  (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
+	   domains[loop->num]);
+      else
+      	ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
+	  (&PBB_DOMAIN (pbb), ph);
+
+      if (doms[loop->num])
+	pbb->domain = isl_set_copy (doms[loop->num]);
+      else
+	pbb->domain = isl_set_copy (scop->context);
+
+      pbb->domain = isl_set_set_tuple_id (pbb->domain,
+					  isl_id_for_pbb (scop, pbb));
+
+    }
 
   for (i = 0; i < nb_loops; i++)
-    if (domains[i])
-      ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
+    {
+      if (domains[i])
+	ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
+
+      if (doms[i])
+	isl_set_free (doms[i]);
+    }
 
   ppl_delete_Polyhedron (ph);
   free (domains);
+
+  free (doms);
 }
 
 /* Add a constrain to the ACCESSES polyhedron for the alias set of
@@ -2459,6 +2592,8 @@  new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb)
     ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
       (&PBB_DOMAIN (pbb1), PBB_DOMAIN (pbb));
 
+  pbb1->domain = isl_set_copy (pbb->domain);
+
   GBB_PBB (gbb1) = pbb1;
   GBB_CONDITIONS (gbb1) = VEC_copy (gimple, heap, GBB_CONDITIONS (gbb));
   GBB_CONDITION_CASES (gbb1) = VEC_copy (gimple, heap, GBB_CONDITION_CASES (gbb));