--- gcc/graphite-clast-to-gimple.c | 55 ++++++-- gcc/graphite-cloog-util.c | 1 + gcc/graphite-poly.c | 8 + gcc/graphite-poly.h | 3 + gcc/graphite-sese-to-poly.c | 299 +++++++++++++++++++++++++++++++++++++++- gcc/graphite.c | 4 + 6 files changed, 354 insertions(+), 16 deletions(-)
diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c index bb0f4c8..9a9effa 100644 --- a/gcc/graphite-clast-to-gimple.c +++ b/gcc/graphite-clast-to-gimple.c @@ -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); diff --git a/gcc/graphite-cloog-util.c b/gcc/graphite-cloog-util.c index 82a49a1..6086864 100644 --- a/gcc/graphite-cloog-util.c +++ b/gcc/graphite-cloog-util.c @@ -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 diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index af40d20..fd2703b 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -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"); } diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h index 72e9530..bb8771d 100644 --- a/gcc/graphite-poly.h +++ b/gcc/graphite-poly.h @@ -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; diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index b7efe41..9723427 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -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); + } } } diff --git a/gcc/graphite.c b/gcc/graphite.c index 8f6d8a1..b2cf7c6 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.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. */ -- 1.7.4.1