@@ -24,6 +24,11 @@ along with GCC; see the file COPYING3. If not see
#include <isl/set.h>
#include <isl/map.h>
#include <isl/union_map.h>
+#include <isl/list.h>
+#include <isl/constraint.h>
+#include <isl/div.h>
+#include <isl/ilp.h>
+#include <isl/aff.h>
#include <cloog/cloog.h>
#include <cloog/isl/domain.h>
#endif
@@ -768,16 +773,19 @@ graphite_create_new_guard (edge entry_edge, struct clast_guard *stmt,
static void
compute_bounds_for_param (scop_p scop, int param, mpz_t low, mpz_t up)
{
- ppl_Linear_Expression_t le;
-
- /* Prepare the linear expression corresponding to the parameter that
- we want to maximize/minimize. */
- ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
- ppl_set_coef (le, param, 1);
-
- ppl_max_for_le_pointset (SCOP_CONTEXT (scop), le, up);
- ppl_min_for_le_pointset (SCOP_CONTEXT (scop), le, low);
- ppl_delete_Linear_Expression (le);
+ isl_int v;
+ isl_aff *aff = isl_aff_zero
+ (isl_local_space_from_dim (isl_set_get_dim (scop->context)));
+
+ aff = isl_aff_add_coefficient_si (aff, isl_dim_param, param, 1);
+
+ isl_int_init (v);
+ isl_set_min (scop->context, aff, &v);
+ isl_int_get_gmp (v, low);
+ isl_set_max (scop->context, aff, &v);
+ isl_int_get_gmp (v, up);
+ isl_int_clear (v);
+ isl_aff_free (aff);
}
/* Compute the lower bound LOW and upper bound UP for the induction
@@ -1357,7 +1365,6 @@ build_cloog_union_domain (scop_p scop)
{
int i;
poly_bb_p pbb;
-
CloogUnionDomain *union_domain =
cloog_union_domain_alloc (scop_nb_params (scop));
@@ -1460,8 +1467,30 @@ generate_cloog_input (scop_p scop, htab_t params_index)
union_domain = add_names_to_union_domain (scop, union_domain,
nb_scattering_dims,
params_index);
- context = new_Cloog_Domain_from_ppl_Pointset_Powerset
- (SCOP_CONTEXT (scop), scop_nb_params (scop), cloog_state);
+
+ if (1)
+ {
+ /* For now remove the isl_id's from the context before
+ translating to CLooG: this code will be removed when the
+ domain will also contain isl_id's. */
+ isl_set *ct = isl_set_project_out (isl_set_copy (scop->context),
+ isl_dim_set, 0, number_of_loops ());
+ isl_printer *p = isl_printer_to_str (scop->ctx);
+ char *str;
+
+ p = isl_printer_set_output_format (p, ISL_FORMAT_EXT_POLYLIB);
+ p = isl_printer_print_set (p, ct);
+ isl_set_free (ct);
+
+ str = isl_printer_get_str (p);
+ ct = isl_set_read_from_str (scop->ctx, str,
+ scop_nb_params (scop));
+ free (str);
+ isl_printer_free (p);
+ context = cloog_domain_from_isl_set (ct);
+ }
+ else
+ context = cloog_domain_from_isl_set (isl_set_copy (scop->context));
cloog_input = cloog_input_alloc (context, union_domain);
@@ -25,6 +25,7 @@ along with GCC; see the file COPYING3. If not see
#include <isl/set.h>
#include <isl/map.h>
#include <isl/union_map.h>
+#include <isl/aff.h>
#include <cloog/cloog.h>
#include <cloog/isl/domain.h>
#endif
@@ -1012,6 +1012,7 @@ new_scop (void *region)
scop_p scop = XNEW (struct scop);
SCOP_CONTEXT (scop) = NULL;
+ scop->context = NULL;
scop_set_region (scop, region);
SCOP_BBS (scop) = VEC_alloc (poly_bb_p, heap, 3);
SCOP_ORIGINAL_PDDRS (scop) = htab_create (10, hash_poly_ddr_p,
@@ -1040,6 +1041,7 @@ free_scop (scop_p scop)
if (SCOP_CONTEXT (scop))
ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop));
+ isl_set_free (scop->context);
htab_delete (SCOP_ORIGINAL_PDDRS (scop));
free_lst (SCOP_ORIGINAL_SCHEDULE (scop));
free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
@@ -1401,6 +1403,12 @@ print_scop_context (FILE *file, scop_p scop, int verbosity)
else
fprintf (file, "0 %d\n", (int) scop_nb_params (scop) + 2);
+ if (scop->context)
+ {
+ isl_printer *p = isl_printer_to_file (scop->ctx, file);
+ isl_printer_print_set (p, scop->context);
+ }
+
if (verbosity > 0)
fprintf (file, "# )\n");
}
@@ -1409,6 +1409,9 @@ struct scop
ppl_Pointset_Powerset_C_Polyhedron_t _context;
isl_set *context;
+ /* The context used internally by ISL. */
+ isl_ctx *ctx;
+
/* A hashtable of the data dependence relations for the original
scattering. */
htab_t original_pddrs;
@@ -24,6 +24,8 @@ along with GCC; see the file COPYING3. If not see
#include <isl/set.h>
#include <isl/map.h>
#include <isl/union_map.h>
+#include <isl/constraint.h>
+#include <isl/aff.h>
#include <cloog/cloog.h>
#include <cloog/cloog.h>
#include <cloog/isl/domain.h>
@@ -595,6 +597,216 @@ build_scop_scattering (scop_p scop)
ppl_delete_Linear_Expression (static_schedule);
}
+static isl_pw_aff *extract_affine (scop_p, tree);
+
+/* Extract an affine expression from the chain of recurrence E. */
+
+static isl_pw_aff *
+extract_affine_chrec (scop_p s, tree e)
+{
+ isl_pw_aff *lhs = extract_affine (s, CHREC_LEFT (e));
+ isl_pw_aff *rhs = extract_affine (s, CHREC_RIGHT (e));
+ isl_dim *dim = isl_dim_set_alloc (s->ctx, 0, number_of_loops ());
+ isl_local_space *ls = isl_local_space_from_dim (dim);
+ isl_aff *loop = isl_aff_set_coefficient_si
+ (isl_aff_zero (ls), isl_dim_set, CHREC_VARIABLE (e), 1);
+ isl_pw_aff *l = isl_pw_aff_from_aff (loop);
+
+ /* Before multiplying, make sure that the result is affine. */
+ gcc_assert (isl_pw_aff_is_cst (rhs)
+ || isl_pw_aff_is_cst (l));
+
+ return isl_pw_aff_add (lhs, isl_pw_aff_mul (rhs, l));
+}
+
+/* Extract an affine expression from the mult_expr E. */
+
+static isl_pw_aff *
+extract_affine_mul (scop_p s, tree e)
+{
+ isl_pw_aff *lhs = extract_affine (s, TREE_OPERAND (e, 0));
+ isl_pw_aff *rhs = extract_affine (s, TREE_OPERAND (e, 1));
+
+ if (!isl_pw_aff_is_cst (lhs)
+ && !isl_pw_aff_is_cst (rhs))
+ {
+ isl_pw_aff_free (lhs);
+ isl_pw_aff_free (rhs);
+ return NULL;
+ }
+
+ return isl_pw_aff_mul (lhs, rhs);
+}
+
+/* Return an ISL identifier from the name of the ssa_name E. */
+
+static isl_id *
+isl_id_for_ssa_name (scop_p s, tree e)
+{
+ const char *name = get_name (e);
+ isl_id *id;
+
+ if (name)
+ id = isl_id_alloc (s->ctx, name, e);
+ else
+ {
+ char name1[50];
+ snprintf (name1, sizeof (name1), "P_%d", SSA_NAME_VERSION (e));
+ id = isl_id_alloc (s->ctx, name1, 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 *
+extract_affine_name (scop_p s, tree e)
+{
+ isl_aff *aff;
+ isl_set *dom;
+ isl_dim *dim = isl_dim_set_alloc (s->ctx, 1, number_of_loops ());
+
+ dim = isl_dim_set_dim_id (dim, isl_dim_param, 0, isl_id_for_ssa_name (s, e));
+ dom = isl_set_universe (isl_dim_copy (dim));
+ aff = isl_aff_zero (isl_local_space_from_dim (dim));
+ aff = isl_aff_add_coefficient_si (aff, isl_dim_param, 0, 1);
+ return isl_pw_aff_alloc (dom, aff);
+}
+
+/* Extract an affine expression from the gmp constant G. */
+
+static isl_pw_aff *
+extract_affine_gmp (scop_p s, mpz_t g)
+{
+ isl_dim *dim = isl_dim_set_alloc (s->ctx, 0, number_of_loops ());
+ isl_local_space *ls = isl_local_space_from_dim (isl_dim_copy (dim));
+ isl_aff *aff = isl_aff_zero (ls);
+ isl_set *dom = isl_set_universe (dim);
+ isl_int v;
+
+ isl_int_init (v);
+ isl_int_set_gmp (v, g);
+ aff = isl_aff_add_constant (aff, v);
+ isl_int_clear (v);
+
+ return isl_pw_aff_alloc (dom, aff);
+}
+
+/* Extract an affine expression from the integer_cst E. */
+
+static isl_pw_aff *
+extract_affine_int (scop_p s, tree e)
+{
+ isl_pw_aff *res;
+ mpz_t g;
+
+ mpz_init (g);
+ tree_int_to_gmp (e, g);
+ res = extract_affine_gmp (s, g);
+ mpz_clear (g);
+
+ return res;
+}
+
+/* Compute pwaff mod 2^width. */
+
+static isl_pw_aff *
+wrap (isl_pw_aff *pwaff, unsigned width)
+{
+ isl_int mod;
+
+ isl_int_init (mod);
+ isl_int_set_si (mod, 1);
+ isl_int_mul_2exp (mod, mod, width);
+
+ pwaff = isl_pw_aff_mod (pwaff, mod);
+
+ isl_int_clear (mod);
+
+ return pwaff;
+}
+
+/* Extract an affine expression from the tree E in the scop S. */
+
+static isl_pw_aff *
+extract_affine (scop_p s, tree e)
+{
+ isl_pw_aff *lhs, *rhs, *res;
+ tree type;
+
+ if (e == chrec_dont_know)
+ return NULL;
+
+ switch (TREE_CODE (e))
+ {
+ case POLYNOMIAL_CHREC:
+ res = extract_affine_chrec (s, e);
+ break;
+
+ case MULT_EXPR:
+ res = extract_affine_mul (s, e);
+ break;
+
+ case PLUS_EXPR:
+ case POINTER_PLUS_EXPR:
+ lhs = extract_affine (s, TREE_OPERAND (e, 0));
+ rhs = extract_affine (s, TREE_OPERAND (e, 1));
+ res = isl_pw_aff_add (lhs, rhs);
+ break;
+
+ case MINUS_EXPR:
+ lhs = extract_affine (s, TREE_OPERAND (e, 0));
+ rhs = extract_affine (s, TREE_OPERAND (e, 1));
+ res = isl_pw_aff_sub (lhs, rhs);
+ break;
+
+ case NEGATE_EXPR:
+ case BIT_NOT_EXPR:
+ lhs = extract_affine (s, TREE_OPERAND (e, 0));
+ rhs = extract_affine (s, integer_minus_one_node);
+ res = isl_pw_aff_mul (lhs, rhs);
+ break;
+
+ case SSA_NAME:
+ res = extract_affine_name (s, e);
+ break;
+
+ case INTEGER_CST:
+ res = extract_affine_int (s, e);
+ break;
+
+ CASE_CONVERT:
+ case NON_LVALUE_EXPR:
+ res = extract_affine (s, TREE_OPERAND (e, 0));
+ break;
+
+ default:
+ gcc_unreachable ();
+ break;
+ }
+
+ type = TREE_TYPE (e);
+ if (TYPE_UNSIGNED (type))
+ res = wrap (res, TYPE_PRECISION (type));
+
+ return res;
+}
+
/* Add the value K to the dimension D of the linear expression EXPR. */
static void
@@ -931,6 +1143,7 @@ find_scop_parameters (scop_p scop)
sese region = SCOP_REGION (scop);
struct loop *loop;
mpz_t one;
+ int nbp;
mpz_init (one);
mpz_set_si (one, 1);
@@ -953,11 +1166,28 @@ find_scop_parameters (scop_p scop)
FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
find_params_in_bb (region, PBB_BLACK_BOX (pbb));
- scop_set_nb_params (scop, sese_nb_params (region));
+ nbp = sese_nb_params (region);
+ scop_set_nb_params (scop, nbp);
SESE_ADD_PARAMS (region) = false;
ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
- (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
+ (&SCOP_CONTEXT (scop), nbp, 0);
+
+ {
+ tree e;
+ unsigned nbl = number_of_loops ();
+ isl_dim *dim = isl_dim_set_alloc (scop->ctx, nbp, nbl);
+
+ FOR_EACH_VEC_ELT (tree, SESE_PARAMS (region), i, e)
+ 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);
+ }
}
/* Insert in the SCOP context constraints from the estimation of the
@@ -1094,6 +1324,7 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop,
ppl_Constraint_t ub;
ppl_Linear_Expression_t ub_expr;
double_int nit;
+ isl_pw_aff *aff;
mpz_init (one);
mpz_set_si (one, 1);
@@ -1102,8 +1333,33 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop,
scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
mpz_clear (one);
+ aff = extract_affine (scop, nb_iters);
+ scop->context = isl_set_intersect
+ (scop->context, isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff)));
+
if (max_stmt_executions (loop, true, &nit))
- add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr);
+ {
+ add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr);
+
+ {
+ /* Insert in the context the constraints from the
+ estimation of the number of iterations NIT and the
+ symbolic number of iterations (involving parameter
+ names) NB_ITERS. First, build the affine expression
+ "NIT - NB_ITERS" and then say that it is positive,
+ i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
+ isl_pw_aff *approx;
+ mpz_t g;
+ isl_set *x;
+
+ mpz_init (g);
+ mpz_set_double_int (g, nit, false);
+ approx = extract_affine_gmp (scop, g);
+ mpz_clear (g);
+ x = isl_pw_aff_ge_set (approx, aff);
+ scop->context = isl_set_intersect (scop->context, x);
+ }
+ }
/* loop_i <= expr_nb_iters */
ppl_set_coef (ub_expr, nb, -1);
@@ -1463,6 +1719,25 @@ add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
ppl_Polyhedron_add_constraint (context, cstr);
ppl_delete_Linear_Expression (le);
ppl_delete_Constraint (cstr);
+
+ {
+ isl_dim *dim = isl_set_get_dim (scop->context);
+ isl_constraint *c = isl_inequality_alloc (dim);
+ mpz_t g;
+ isl_int v;
+
+ mpz_init (g);
+ isl_int_init (v);
+ tree_int_to_gmp (lb, g);
+ isl_int_set_gmp (v, g);
+ isl_int_neg (v, v);
+ mpz_clear (g);
+ c = isl_constraint_set_constant (c, v);
+ isl_int_clear (v);
+ c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, 1);
+
+ scop->context = isl_set_add_constraint (scop->context, c);
+ }
}
if (ub)
@@ -1474,6 +1749,24 @@ add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
ppl_Polyhedron_add_constraint (context, cstr);
ppl_delete_Linear_Expression (le);
ppl_delete_Constraint (cstr);
+
+ {
+ isl_dim *dim = isl_set_get_dim (scop->context);
+ isl_constraint *c = isl_inequality_alloc (dim);
+ mpz_t g;
+ isl_int v;
+
+ mpz_init (g);
+ isl_int_init (v);
+ tree_int_to_gmp (ub, g);
+ isl_int_set_gmp (v, g);
+ mpz_clear (g);
+ c = isl_constraint_set_constant (c, v);
+ isl_int_clear (v);
+ c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, -1);
+
+ scop->context = isl_set_add_constraint (scop->context, c);
+ }
}
}
@@ -260,10 +260,12 @@ graphite_transform_loops (void)
bool need_cfg_cleanup_p = false;
VEC (scop_p, heap) *scops = NULL;
htab_t bb_pbb_mapping;
+ isl_ctx *ctx;
if (!graphite_initialize ())
return;
+ ctx = isl_ctx_alloc ();
build_scops (&scops);
if (dump_file && (dump_flags & TDF_DETAILS))
@@ -277,6 +279,7 @@ graphite_transform_loops (void)
FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
if (dbg_cnt (graphite_scop))
{
+ scop->ctx = ctx;
build_poly_scop (scop);
if (POLY_SCOP_P (scop)
@@ -288,6 +291,7 @@ graphite_transform_loops (void)
htab_delete (bb_pbb_mapping);
free_scops (scops);
graphite_finalize (need_cfg_cleanup_p);
+ isl_ctx_free (ctx);
}
#else /* If Cloog is not available: #ifndef HAVE_cloog. */