On Thu, Aug 11, 2011 at 05:44:37PM -0500, Sebastian Pop wrote:
>
> Signed-off-by: Sebastian Pop <seb...@gmail.com>
> ---
> 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 | 301
> +++++++++++++++++++++++++++++++++++++++-
> gcc/graphite.c | 4 +
> 6 files changed, 356 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..69392a9 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,26 @@ 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);
> + isl_constraint_set_constant (c, v);
> + isl_int_set_si (v, 1);
> + isl_constraint_set_coefficient (c, isl_dim_param, p, v);
> + isl_int_clear (v);
> +
> + scop->context = isl_set_add_constraint (scop->context, c);
> + }
> }
>
> if (ub)
> @@ -1474,6 +1750,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 (ub, g);
> + isl_int_set_gmp (v, g);
> + mpz_clear (g);
> + isl_constraint_set_constant (c, v);
> + isl_int_set_si (v, -1);
> + isl_constraint_set_coefficient (c, isl_dim_param, p, v);
> + isl_int_clear (v);
> +
> + 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
Sebastian,
This patch falls to compile under clang3.0svn with the error...
../../gcc-4.7-20110811/gcc/graphite-sese-to-poly.c:643:8: error: unknown type
name 'isl_id'
static isl_id *
^
../../gcc-4.7-20110811/gcc/graphite-sese-to-poly.c:647:3: error: use of
undeclared identifier 'isl_id'
isl_id *id;
Did you omit some of the patch?
Jack
