diff options
Diffstat (limited to 'gcc/graphite-poly.c')
| -rw-r--r-- | gcc/graphite-poly.c | 1033 |
1 files changed, 196 insertions, 837 deletions
diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index 9f3ba1d..e3563a2 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -1,5 +1,5 @@ /* Graphite polyhedral representation. - Copyright (C) 2009, 2010 Free Software Foundation, Inc. + Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc. Contributed by Sebastian Pop <sebastian.pop@amd.com> and Tobias Grosser <grosser@fim.uni-passau.de>. @@ -18,7 +18,20 @@ GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see <http://www.gnu.org/licenses/>. */ + #include "config.h" + +#ifdef HAVE_cloog +#include <isl/set.h> +#include <isl/map.h> +#include <isl/union_map.h> +#include <isl/constraint.h> +#include <isl/ilp.h> +#include <isl/aff.h> +#include <cloog/cloog.h> +#include <cloog/isl/domain.h> +#endif + #include "system.h" #include "coretypes.h" #include "diagnostic-core.h" @@ -32,14 +45,24 @@ along with GCC; see the file COPYING3. If not see #include "sese.h" #ifdef HAVE_cloog -#include "ppl_c.h" -#include "graphite-ppl.h" #include "graphite-poly.h" -#include "graphite-dependences.h" -#include "graphite-cloog-util.h" #define OPENSCOP_MAX_STRING 256 + +/* Print to STDERR the GMP value VAL. */ + +DEBUG_FUNCTION void +debug_gmp_value (mpz_t val) +{ + char *str = mpz_get_str (0, 10, val); + void (*gmp_free) (void *, size_t); + + fprintf (stderr, "%s", str); + mp_get_memory_functions (NULL, NULL, &gmp_free); + (*gmp_free) (str, strlen (str) + 1); +} + /* Return the maximal loop depth in SCOP. */ int @@ -59,223 +82,6 @@ scop_max_loop_depth (scop_p scop) return max_nb_loops; } -/* Extend the scattering matrix of PBB to MAX_SCATTERING scattering - dimensions. */ - -static void -extend_scattering (poly_bb_p pbb, int max_scattering) -{ - ppl_dimension_type nb_old_dims, nb_new_dims; - int nb_added_dims, i; - ppl_Coefficient_t coef; - mpz_t one; - - nb_added_dims = max_scattering - pbb_nb_scattering_transform (pbb); - mpz_init (one); - mpz_set_si (one, 1); - ppl_new_Coefficient (&coef); - ppl_assign_Coefficient_from_mpz_t (coef, one); - - gcc_assert (nb_added_dims >= 0); - - nb_old_dims = pbb_nb_scattering_transform (pbb) + pbb_dim_iter_domain (pbb) - + scop_nb_params (PBB_SCOP (pbb)); - nb_new_dims = nb_old_dims + nb_added_dims; - - ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), - pbb_nb_scattering_transform (pbb), nb_added_dims); - PBB_NB_SCATTERING_TRANSFORM (pbb) += nb_added_dims; - - /* Add identity matrix for the added dimensions. */ - for (i = max_scattering - nb_added_dims; i < max_scattering; i++) - { - ppl_Constraint_t cstr; - ppl_Linear_Expression_t expr; - - ppl_new_Linear_Expression_with_dimension (&expr, nb_new_dims); - ppl_Linear_Expression_add_to_coefficient (expr, i, coef); - ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL); - ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr); - ppl_delete_Constraint (cstr); - ppl_delete_Linear_Expression (expr); - } - - ppl_delete_Coefficient (coef); - mpz_clear (one); -} - -/* All scattering matrices in SCOP will have the same number of scattering - dimensions. */ - -int -unify_scattering_dimensions (scop_p scop) -{ - int i; - poly_bb_p pbb; - graphite_dim_t max_scattering = 0; - - FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) - max_scattering = MAX (pbb_nb_scattering_transform (pbb), max_scattering); - - FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) - extend_scattering (pbb, max_scattering); - - return max_scattering; -} - -/* Print to FILE the pdr PH in OpenScop format. NB_SUBSCRIPTS is the number - of subscripts in PH, ALIAS_SET_DIM is the dimension of the alias set and - NB_PARAMS is the number of parameters in PH. */ - -static void -openscop_print_pdr_polyhedron (FILE *file, ppl_const_Polyhedron_t ph, - int nb_subscripts, int alias_set_dimension, - int nb_params) -{ - int input, locals, output; - ppl_dimension_type alias_set_dim = (ppl_dimension_type) alias_set_dimension; - ppl_dimension_type sub_dim_last = alias_set_dim + nb_subscripts; - ppl_dimension_type *map, i, ph_space_dim = sub_dim_last + 1; - ppl_Polyhedron_t pph; - - ppl_new_C_Polyhedron_from_C_Polyhedron (&pph, ph); - - map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, ph_space_dim); - - for (i = 0; i < alias_set_dim - 1; i++) - map[i] = nb_subscripts + 1 + i; - - for (i = alias_set_dim - 1; i < sub_dim_last; i++) - map[i] = i - alias_set_dim + 1; - - ppl_Polyhedron_map_space_dimensions (pph, map, ph_space_dim - 1); - - locals = 0; - input = alias_set_dim - nb_params - 1; - - /* According to OpenScop specification, the alias set column is a part of - the output columns. */ - output = nb_subscripts + 1; - - openscop_print_polyhedron_matrix (file, pph, output, input, locals, nb_params); -} - -/* Print to FILE the powerset PDR. NB_SUBSCRIPTS is the number of subscripts - in PDR, ALIAS_SET_DIM is the dimension of the alias set in PDR and - NB_PARAMS is the number of parameters in PDR. */ - -static void -openscop_print_pdr_powerset (FILE *file, - ppl_Pointset_Powerset_C_Polyhedron_t ps, - int nb_subscripts, - int alias_set_dim, - int nb_params) -{ - size_t nb_disjuncts; - 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); - - ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts); - fprintf (file, "%d\n", (int) nb_disjuncts); - - for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it), - ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end); - !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end); - ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it)) - { - ppl_const_Polyhedron_t ph; - - ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph); - openscop_print_pdr_polyhedron (file, ph, nb_subscripts, alias_set_dim, - nb_params); - } - - ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it); - ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end); -} - -/* Print to FILE the powerset PS in its OpenScop matrix form. */ - -static void -openscop_print_powerset_matrix (FILE *file, - ppl_Pointset_Powerset_C_Polyhedron_t ps, - int output, int input, int locals, - int params) -{ - size_t nb_disjuncts; - 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); - - ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts); - fprintf (file, "%d\n", (int) nb_disjuncts); - - for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it), - ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end); - !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end); - ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it)) - { - ppl_const_Polyhedron_t ph; - - ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph); - openscop_print_polyhedron_matrix (file, ph, output, input, locals, - params); - } - - ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it); - ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end); -} - -/* Prints to FILE the scattering function of PBB in OpenScop format, at some - VERBOSITY level. */ - -static void -openscop_print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity) -{ - graphite_dim_t i; - ppl_const_Polyhedron_t ph; - - if (verbosity > 0) - { - fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb)); - fprintf (file, "#eq"); - - for (i = 0; i < pbb_nb_scattering_transform (pbb); i++) - fprintf (file, " s%d", (int) i); - - for (i = 0; i < pbb_nb_local_vars (pbb); i++) - fprintf (file, " lv%d", (int) i); - - for (i = 0; i < pbb_dim_iter_domain (pbb); i++) - fprintf (file, " i%d", (int) i); - - for (i = 0; i < pbb_nb_params (pbb); i++) - fprintf (file, " p%d", (int) i); - - fprintf (file, " cst\n"); - } - - /* Number of disjunct components. Remove this when - PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */ - fprintf (file, "1\n"); - - ph = PBB_TRANSFORMED_SCATTERING (pbb) - ? PBB_TRANSFORMED_SCATTERING (pbb) - : PBB_ORIGINAL_SCATTERING (pbb); - - openscop_print_polyhedron_matrix (file, ph, - pbb_nb_scattering_transform (pbb), - pbb_dim_iter_domain (pbb), - pbb_nb_local_vars (pbb), - pbb_nb_params (pbb)); - - if (verbosity > 0) - fprintf (file, "#)\n"); -} - /* Prints to FILE the scattering function of PBB, at some VERBOSITY level. */ @@ -304,12 +110,8 @@ print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity) fprintf (file, " cst\n"); } - /* Number of disjunct components. Remove this when - PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */ - fprintf (file, "1\n"); - ppl_print_polyhedron_matrix (file, PBB_TRANSFORMED_SCATTERING (pbb) - ? PBB_TRANSFORMED_SCATTERING (pbb) - : PBB_ORIGINAL_SCATTERING (pbb)); + fprintf (file, "isl\n"); + print_isl_map (file, pbb->transformed ? pbb->transformed : pbb->schedule); if (verbosity > 0) fprintf (file, "#)\n"); @@ -324,8 +126,7 @@ print_scattering_function (FILE *file, poly_bb_p pbb, int verbosity) if (!PBB_TRANSFORMED (pbb)) return; - if (PBB_TRANSFORMED_SCATTERING (pbb) - || PBB_ORIGINAL_SCATTERING (pbb)) + if (pbb->schedule || pbb->transformed) { if (verbosity > 0) fprintf (file, "# Scattering function is provided\n"); @@ -341,7 +142,7 @@ print_scattering_function (FILE *file, poly_bb_p pbb, int verbosity) return; } - openscop_print_scattering_function_1 (file, pbb, verbosity); + print_scattering_function_1 (file, pbb, verbosity); if (verbosity > 0) fprintf (file, "# Scattering names are not provided\n"); @@ -420,334 +221,12 @@ debug_iteration_domains (scop_p scop, int verbosity) print_iteration_domains (stderr, scop, verbosity); } -/* Read N integer from FILE. */ - -int * -openscop_read_N_int (FILE *file, int N) -{ - char s[OPENSCOP_MAX_STRING]; - char *str; - int i, *res = (int *) xmalloc (OPENSCOP_MAX_STRING * sizeof (int)); - - /* Skip blank and commented lines. */ - while (fgets (s, sizeof s, file) == (char *) 0 - || s[0] == '#' - || ISSPACE (s[0])) - ; - - str = s; - - for (i = 0; i < N; i++) - { - sscanf (str, "%d", &res[i]); - - /* Jump the integer that was read. */ - while ((*str) && !ISSPACE (*str) && (*str != '#')) - str++; - - /* Jump spaces. */ - while ((*str) && ISSPACE (*str) && (*str != '#')) - str++; - } - - return res; -} - -/* Read one integer from FILE. */ - -static int -openscop_read_one_int (FILE *file) -{ - int *x = openscop_read_N_int (file, 1); - int res = *x; - - free (x); - return res; -} - -/* Read N string from FILE. */ - -static char * -openscop_read_N_string (FILE *file, int N) -{ - int count, i; - char str[OPENSCOP_MAX_STRING]; - char *tmp = (char *) xmalloc (sizeof (char) * OPENSCOP_MAX_STRING); - char *s = NULL; - - /* Skip blank and commented lines. */ - while (fgets (str, sizeof str, file) == (char *) 0 - || str[0] == '#' - || ISSPACE (str[0])) - ; - - s = str; - count = 0; - - for (i = 0; i < N; i++) - { - /* Read the first word. */ - for (; (*s) && (!ISSPACE (*s)) && (*s != '#'); ++count) - tmp[count] = *(s++); - - tmp[count] = ' '; - count++; - - /* Jump spaces. */ - while ((*s) && ISSPACE (*s) && (*s != '#')) - s++; - } - - tmp[count-1] = '\0'; - - return tmp; -} - -/* Read one string from FILE. */ - -static char * -openscop_read_one_string (FILE *file) -{ - return openscop_read_N_string (file, 1); -} - -/* Read from FILE the powerset PS in its OpenScop matrix form. OUTPUT is the - number of output dimensions, INPUT is the number of input dimensions, - LOCALS is the number of existentially quantified variables and PARAMS is - the number of parameters. */ - -static void -openscop_read_powerset_matrix (FILE *file, - ppl_Pointset_Powerset_C_Polyhedron_t *ps, - int *output, int *input, int *locals, - int *params) -{ - int nb_disjuncts, i; - - nb_disjuncts = openscop_read_one_int (file); - - for (i = 0; i < nb_disjuncts; i++) - { - ppl_Polyhedron_t ph; - - openscop_read_polyhedron_matrix (file, &ph, output, input, locals, - params); - if (!ph) - *ps = NULL; - else if (i == 0) - ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (ps, ph); - else - ppl_Pointset_Powerset_C_Polyhedron_add_disjunct (*ps, ph); - } -} - -/* Read a scattering function from FILE and save it to PBB. Return whether - the scattering function was provided or not. */ - -static bool -graphite_read_scatt (FILE *file, poly_bb_p pbb) -{ - bool scattering_provided = false; - int output, input, locals, params; - ppl_Polyhedron_t newp; - - if (openscop_read_one_int (file) > 0) - { - /* Read number of disjunct components. */ - openscop_read_one_int (file); - - /* Read scattering function. */ - openscop_read_polyhedron_matrix (file, &newp, &output, &input, - &locals, ¶ms); - store_scattering (PBB_SCOP (pbb)); - PBB_TRANSFORMED (pbb) = poly_scattering_new (); - PBB_TRANSFORMED_SCATTERING (pbb) = newp; - PBB_NB_LOCAL_VARIABLES (pbb) = locals; - - /* New scattering dimension. */ - PBB_NB_SCATTERING_TRANSFORM (pbb) = output; - - scattering_provided = true; - } - - return scattering_provided; -} - -/* Read a scop file. Return true if the scop is transformed. */ - -static bool -graphite_read_scop_file (FILE *file, scop_p scop) -{ - char *tmp, *language; - size_t i, j, nb_statements, nbr, nbw; - int input, output, locals, params; - ppl_Pointset_Powerset_C_Polyhedron_t ps; - poly_bb_p pbb; - bool transform_done = false; - - /* Ensure that the file is in OpenScop format. */ - tmp = openscop_read_N_string (file, 2); - - if (strcmp (tmp, "SCoP 1")) - { - error ("the file is not in OpenScop format"); - return false; - } - - free (tmp); - - /* Read the language. */ - language = openscop_read_one_string (file); - - if (strcmp (language, "Gimple")) - { - error ("the language is not recognized"); - return false; - } - - free (language); - - /* Read the context but do not use it. */ - openscop_read_powerset_matrix (file, &ps, &input, &output, &locals, ¶ms); - - if ((size_t) params != scop->nb_params) - { - error ("parameters number in the scop file is different from the" - " internal scop parameter number"); - return false; - } - - /* Read parameter names if provided. */ - if (openscop_read_one_int (file)) - openscop_read_N_string (file, scop->nb_params); - - nb_statements = openscop_read_one_int (file); - - if (nb_statements != VEC_length (poly_bb_p, SCOP_BBS (scop))) - { - error ("number of statements in the OpenScop file does not match" - " the graphite internal statements number"); - return false; - } - - for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) - { - /* Read iteration domain. */ - openscop_read_powerset_matrix (file, &ps, &input, &output, &locals, - ¶ms); - - /* Read scattering. */ - transform_done = graphite_read_scatt (file, pbb); - - /* Scattering names. */ - openscop_read_one_int (file); - - /* Read access functions. */ - if (openscop_read_one_int (file) > 0) - { - nbr = openscop_read_one_int (file); - - /* Read access functions. */ - for (j = 0; j < nbr; j++) - openscop_read_powerset_matrix (file, &ps, &input, &output, &locals, - ¶ms); - - nbw = openscop_read_one_int (file); - - /* Write access functions. */ - for (j = 0; j < nbw; j++) - openscop_read_powerset_matrix (file, &ps, &input, &output, &locals, - ¶ms); - } - - /* Statement body. */ - openscop_read_one_int (file); - } - - return transform_done; -} - -/* Initialize and return a file that will be used to write a scop. SCOP_NUMBER - is a sequential number (identifier) used to differentiate scop files. - Examples of the generated file names: dump_base_name.0.graphite, - dump_base_name.1.graphite, dump_base_name.2.graphite, etc. */ - -static FILE * -init_graphite_out_file (int scop_number) -{ - FILE *graphite_out_file; - int len = strlen (dump_base_name); - char *dumpname = XNEWVEC (char, len + 25); - char *s_scop_number = XNEWVEC (char, 15); - - memcpy (dumpname, dump_base_name, len + 1); - strip_off_ending (dumpname, len); - sprintf (s_scop_number, ".%d", scop_number); - strcat (dumpname, s_scop_number); - strcat (dumpname, ".graphite"); - graphite_out_file = fopen (dumpname, "w+b"); - - if (graphite_out_file == 0) - fatal_error ("can%'t open %s for writing: %m", dumpname); - - free (dumpname); - - return graphite_out_file; -} - -/* Open and return a file used for scop reading. SCOP_NUMBER is a sequential - number (identifier) used to differentiate scop files. Examples of the - generated file names: dump_base_name.0.graphite, dump_base_name.1.graphite, - dump_base_name.2.graphite, etc. */ - -static FILE * -init_graphite_in_file (int scop_number) -{ - FILE *graphite_in_file; - int len = strlen (dump_base_name); - char *dumpname = XNEWVEC (char, len + 25); - char *s_scop_number = XNEWVEC (char, 15); - - memcpy (dumpname, dump_base_name, len + 1); - strip_off_ending (dumpname, len); - sprintf (s_scop_number, ".%d", scop_number); - strcat (dumpname, s_scop_number); - strcat (dumpname, ".graphite"); - graphite_in_file = fopen (dumpname, "r+b"); - - if (graphite_in_file == 0) - fatal_error ("can%'t open %s for reading: %m", dumpname); - - free (dumpname); - - return graphite_in_file; -} - /* Apply graphite transformations to all the basic blocks of SCOP. */ bool apply_poly_transforms (scop_p scop) { bool transform_done = false; - FILE *graphite_file; - static size_t file_scop_number = 0; - - /* This feature is only enabled in the Graphite branch. */ - if (0) - { - graphite_file = init_graphite_in_file (file_scop_number); - transform_done |= graphite_read_scop_file (graphite_file, scop); - - /* We cannot check for the legality of the transform here: there - are cases where graphite_legal_transform cannot determine the - dependence at compile time. For an example, see the - explanation of why http://gcc.gnu.org/PR45450 is invalid. */ - if (0 && !graphite_legal_transform (scop)) - fatal_error ("the graphite file read for scop %d does not contain a legal transform", - (int) file_scop_number); - - file_scop_number++; - } /* Generate code even if we did not apply any real transformation. This also allows to check the performance for the identity @@ -771,70 +250,17 @@ apply_poly_transforms (scop_p scop) transform_done |= scop_do_interchange (scop); } - /* This feature is only enabled in the Graphite branch. */ - if (0) - { - graphite_file = init_graphite_out_file (file_scop_number); - print_scop (graphite_file, scop, 1); - file_scop_number++; - } - return transform_done; } -/* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and - their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same. */ - -static inline bool -can_collapse_pdrs (poly_dr_p pdr1, poly_dr_p pdr2) -{ - bool res; - ppl_Pointset_Powerset_C_Polyhedron_t af1, af2, diff; - - if (PDR_PBB (pdr1) != PDR_PBB (pdr2) - || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2) - || PDR_TYPE (pdr1) != PDR_TYPE (pdr2)) - return false; - - af1 = PDR_ACCESSES (pdr1); - af2 = PDR_ACCESSES (pdr2); - ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron - (&diff, af1); - ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff, af2); - - res = ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff); - ppl_delete_Pointset_Powerset_C_Polyhedron (diff); - return res; -} - -/* Removes duplicated data references in PBB. */ - -void -pbb_remove_duplicate_pdrs (poly_bb_p pbb) -{ - int i, j; - poly_dr_p pdr1, pdr2; - - FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr1) - for (j = i + 1; VEC_iterate (poly_dr_p, PBB_DRS (pbb), j, pdr2); j++) - if (can_collapse_pdrs (pdr1, pdr2)) - { - PDR_NB_REFS (pdr1) += PDR_NB_REFS (pdr2); - free_poly_dr (pdr2); - VEC_ordered_remove (poly_dr_p, PBB_DRS (pbb), j); - } - - PBB_PDR_DUPLICATES_REMOVED (pbb) = true; -} - /* Create a new polyhedral data reference and add it to PBB. It is defined by its ACCESSES, its TYPE, and the number of subscripts NB_SUBSCRIPTS. */ void new_poly_dr (poly_bb_p pbb, int dr_base_object_set, - ppl_Pointset_Powerset_C_Polyhedron_t accesses, - enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts) + enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts, + isl_map *acc, isl_set *extent) { static int id = 0; poly_dr_p pdr = XNEW (struct poly_dr); @@ -843,7 +269,8 @@ new_poly_dr (poly_bb_p pbb, int dr_base_object_set, PDR_BASE_OBJECT_SET (pdr) = dr_base_object_set; PDR_NB_REFS (pdr) = 1; PDR_PBB (pdr) = pbb; - PDR_ACCESSES (pdr) = accesses; + pdr->accesses = acc; + pdr->extent = extent; PDR_TYPE (pdr) = type; PDR_CDR (pdr) = cdr; PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts; @@ -855,7 +282,8 @@ new_poly_dr (poly_bb_p pbb, int dr_base_object_set, void free_poly_dr (poly_dr_p pdr) { - ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr)); + isl_map_free (pdr->accesses); + isl_set_free (pdr->extent); XDELETE (pdr); } @@ -866,7 +294,10 @@ 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->schedule = NULL; + pbb->transformed = NULL; + pbb->saved = NULL; PBB_SCOP (pbb) = scop; pbb_set_black_box (pbb, black_box); PBB_TRANSFORMED (pbb) = NULL; @@ -874,7 +305,6 @@ new_poly_bb (scop_p scop, void *black_box) PBB_ORIGINAL (pbb) = NULL; PBB_DRS (pbb) = VEC_alloc (poly_dr_p, heap, 3); PBB_IS_REDUCTION (pbb) = false; - PBB_PDR_DUPLICATES_REMOVED (pbb) = false; GBB_PBB ((gimple_bb_p) black_box) = pbb; return pbb; @@ -888,16 +318,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_TRANSFORMED (pbb)) - poly_scattering_free (PBB_TRANSFORMED (pbb)); - - if (PBB_SAVED (pbb)) - poly_scattering_free (PBB_SAVED (pbb)); - - if (PBB_ORIGINAL (pbb)) - poly_scattering_free (PBB_ORIGINAL (pbb)); + isl_set_free (pbb->domain); + isl_map_free (pbb->schedule); + isl_map_free (pbb->transformed); + isl_map_free (pbb->saved); if (PBB_DRS (pbb)) FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr) @@ -934,8 +358,6 @@ print_pdr_access_layout (FILE *file, poly_bb_p pbb, poly_dr_p pdr) void print_pdr (FILE *file, poly_dr_p pdr, int verbosity) { - int alias_set_dim; - if (verbosity > 1) { fprintf (file, "# pdr_%d (", PDR_ID (pdr)); @@ -967,13 +389,7 @@ print_pdr (FILE *file, poly_dr_p pdr, int verbosity) print_pdr_access_layout (file, PDR_PBB (pdr), pdr); } - alias_set_dim = pdr_alias_set_dim (pdr) + 1; - - openscop_print_pdr_powerset (file, - PDR_ACCESSES (pdr), - PDR_NB_SUBSCRIPTS (pdr), - alias_set_dim, - pbb_nb_params (PDR_PBB (pdr))); + /* XXX isl dump accesses/subscripts */ if (verbosity > 0) fprintf (file, "#)\n"); @@ -998,11 +414,21 @@ new_scop (void *region) { scop_p scop = XNEW (struct scop); - SCOP_CONTEXT (scop) = NULL; + scop->context = NULL; + scop->must_raw = NULL; + scop->may_raw = NULL; + scop->must_raw_no_source = NULL; + scop->may_raw_no_source = NULL; + scop->must_war = NULL; + scop->may_war = NULL; + scop->must_war_no_source = NULL; + scop->may_war_no_source = NULL; + scop->must_waw = NULL; + scop->may_waw = NULL; + scop->must_waw_no_source = NULL; + scop->may_waw_no_source = 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, - eq_poly_ddr_p, free_poly_ddr); SCOP_ORIGINAL_SCHEDULE (scop) = NULL; SCOP_TRANSFORMED_SCHEDULE (scop) = NULL; SCOP_SAVED_SCHEDULE (scop) = NULL; @@ -1024,10 +450,19 @@ free_scop (scop_p scop) VEC_free (poly_bb_p, heap, SCOP_BBS (scop)); - if (SCOP_CONTEXT (scop)) - ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop)); - - htab_delete (SCOP_ORIGINAL_PDDRS (scop)); + isl_set_free (scop->context); + isl_union_map_free (scop->must_raw); + isl_union_map_free (scop->may_raw); + isl_union_map_free (scop->must_raw_no_source); + isl_union_map_free (scop->may_raw_no_source); + isl_union_map_free (scop->must_war); + isl_union_map_free (scop->may_war); + isl_union_map_free (scop->must_war_no_source); + isl_union_map_free (scop->may_war_no_source); + isl_union_map_free (scop->must_waw); + isl_union_map_free (scop->may_waw); + isl_union_map_free (scop->must_waw_no_source); + isl_union_map_free (scop->may_waw_no_source); free_lst (SCOP_ORIGINAL_SCHEDULE (scop)); free_lst (SCOP_TRANSFORMED_SCHEDULE (scop)); free_lst (SCOP_SAVED_SCHEDULE (scop)); @@ -1043,7 +478,7 @@ openscop_print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity) graphite_dim_t i; gimple_bb_p gbb = PBB_BLACK_BOX (pbb); - if (!PBB_DOMAIN (pbb)) + if (!pbb->domain) return; if (verbosity > 0) @@ -1060,14 +495,7 @@ openscop_print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity) fprintf (file, " cst\n"); } - if (PBB_DOMAIN (pbb)) - openscop_print_powerset_matrix (file, PBB_DOMAIN (pbb), - pbb_dim_iter_domain (pbb), - 0, - 0, - pbb_nb_params (pbb)); - else - fprintf (file, "0\n"); + fprintf (file, "XXX isl\n"); if (verbosity > 0) fprintf (file, "#)\n"); @@ -1076,35 +504,9 @@ openscop_print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity) /* Print to FILE the domain of PBB, at some VERBOSITY level. */ void -print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity) +print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity ATTRIBUTE_UNUSED) { - graphite_dim_t i; - gimple_bb_p gbb = PBB_BLACK_BOX (pbb); - - if (!PBB_DOMAIN (pbb)) - return; - - if (verbosity > 0) - { - fprintf (file, "# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index); - fprintf (file, "# eq"); - - for (i = 0; i < pbb_dim_iter_domain (pbb); i++) - fprintf (file, " i%d", (int) i); - - for (i = 0; i < pbb_nb_params (pbb); i++) - fprintf (file, " p%d", (int) i); - - fprintf (file, " cst\n"); - } - - if (PBB_DOMAIN (pbb)) - ppl_print_powerset_matrix (file, PBB_DOMAIN (pbb)); - else - fprintf (file, "0\n"); - - if (verbosity > 0) - fprintf (file, "#)\n"); + print_isl_set (file, pbb->domain); } /* Dump the cases of a graphite basic block GBB on FILE. */ @@ -1354,9 +756,9 @@ openscop_print_scop_context (FILE *file, scop_p scop, int verbosity) fprintf (file, " cst\n"); } - if (SCOP_CONTEXT (scop)) - openscop_print_powerset_matrix (file, SCOP_CONTEXT (scop), 0, 0, 0, - scop_nb_params (scop)); + if (scop->context) + /* XXX isl print context */ + fprintf (file, "XXX isl\n"); else fprintf (file, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop) + 2, (int) scop_nb_params (scop)); @@ -1383,10 +785,10 @@ print_scop_context (FILE *file, scop_p scop, int verbosity) fprintf (file, " cst\n"); } - if (SCOP_CONTEXT (scop)) - ppl_print_powerset_matrix (file, SCOP_CONTEXT (scop)); + if (scop->context) + print_isl_set (file, scop->context); else - fprintf (file, "0 %d\n", (int) scop_nb_params (scop) + 2); + fprintf (file, "no isl context %d\n", (int) scop_nb_params (scop) + 2); if (verbosity > 0) fprintf (file, "# )\n"); @@ -1476,13 +878,10 @@ print_cloog (FILE *file, scop_p scop, int verbosity) fprintf (file, "# Number of scattering functions\n"); fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop))); - unify_scattering_dimensions (scop); FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) { - if (!PBB_TRANSFORMED (pbb) - || !(PBB_TRANSFORMED_SCATTERING (pbb) - || PBB_ORIGINAL_SCATTERING (pbb))) + if (!(pbb->transformed || pbb->schedule)) continue; if (verbosity > 1) @@ -1554,66 +953,61 @@ debug_scop_params (scop_p scop, int verbosity) print_scop_params (stderr, scop, verbosity); } - -/* The dimension in the transformed scattering polyhedron of PBB - containing the scattering iterator for the loop at depth LOOP_DEPTH. */ - -ppl_dimension_type -psct_scattering_dim_for_loop_depth (poly_bb_p pbb, graphite_dim_t loop_depth) +extern isl_ctx *the_isl_ctx; +void +print_isl_set (FILE *f, isl_set *set) { - ppl_const_Constraint_System_t pcs; - ppl_Constraint_System_const_iterator_t cit, cend; - ppl_const_Constraint_t cstr; - ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb); - ppl_dimension_type iter = psct_iterator_dim (pbb, loop_depth); - ppl_Linear_Expression_t expr; - ppl_Coefficient_t coef; - mpz_t val; - graphite_dim_t i; - - mpz_init (val); - ppl_new_Coefficient (&coef); - ppl_Polyhedron_get_constraints (ph, &pcs); - ppl_new_Constraint_System_const_iterator (&cit); - ppl_new_Constraint_System_const_iterator (&cend); + isl_printer *p = isl_printer_to_file (the_isl_ctx, f); + p = isl_printer_print_set (p, set); + isl_printer_free (p); +} - for (ppl_Constraint_System_begin (pcs, cit), - ppl_Constraint_System_end (pcs, cend); - !ppl_Constraint_System_const_iterator_equal_test (cit, cend); - ppl_Constraint_System_const_iterator_increment (cit)) - { - ppl_Constraint_System_const_iterator_dereference (cit, &cstr); - ppl_new_Linear_Expression_from_Constraint (&expr, cstr); - ppl_Linear_Expression_coefficient (expr, iter, coef); - ppl_Coefficient_to_mpz_t (coef, val); +DEBUG_FUNCTION void +debug_isl_set (isl_set *set) +{ + print_isl_set (stderr, set); +} - if (mpz_sgn (val) == 0) - { - ppl_delete_Linear_Expression (expr); - continue; - } +void +print_isl_map (FILE *f, isl_map *map) +{ + isl_printer *p = isl_printer_to_file (the_isl_ctx, f); + p = isl_printer_print_map (p, map); + isl_printer_free (p); +} - for (i = 0; i < pbb_nb_scattering_transform (pbb); i++) - { - ppl_dimension_type scatter = psct_scattering_dim (pbb, i); +DEBUG_FUNCTION void +debug_isl_map (isl_map *map) +{ + print_isl_map (stderr, map); +} - ppl_Linear_Expression_coefficient (expr, scatter, coef); - ppl_Coefficient_to_mpz_t (coef, val); +void +print_isl_aff (FILE *f, isl_aff *aff) +{ + isl_printer *p = isl_printer_to_file (the_isl_ctx, f); + p = isl_printer_print_aff (p, aff); + isl_printer_free (p); +} - if (mpz_sgn (val) != 0) - { - mpz_clear (val); - ppl_delete_Linear_Expression (expr); - ppl_delete_Coefficient (coef); - ppl_delete_Constraint_System_const_iterator (cit); - ppl_delete_Constraint_System_const_iterator (cend); +DEBUG_FUNCTION void +debug_isl_aff (isl_aff *aff) +{ + print_isl_aff (stderr, aff); +} - return scatter; - } - } - } +void +print_isl_constraint (FILE *f, isl_constraint *c) +{ + isl_printer *p = isl_printer_to_file (the_isl_ctx, f); + p = isl_printer_print_constraint (p, c); + isl_printer_free (p); +} - gcc_unreachable (); +DEBUG_FUNCTION void +debug_isl_constraint (isl_constraint *c) +{ + print_isl_constraint (stderr, c); } /* Returns the number of iterations RES of the loop around PBB at @@ -1624,112 +1018,37 @@ pbb_number_of_iterations_at_time (poly_bb_p pbb, graphite_dim_t time_depth, mpz_t res) { - ppl_Pointset_Powerset_C_Polyhedron_t domain, sctr_lb, sctr_ub; - ppl_dimension_type domain_dim, sctr_dim; - graphite_dim_t dim_iter_domain = pbb_dim_iter_domain (pbb); - ppl_Linear_Expression_t le; - mpz_t lb, ub, diff, one; - int i; + isl_set *transdomain; + isl_space *dc; + isl_aff *aff; + isl_int isllb, islub; - ppl_Polyhedron_space_dimension (PBB_TRANSFORMED_SCATTERING (pbb), &sctr_dim); + isl_int_init (isllb); + isl_int_init (islub); - ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron - (&domain, PBB_DOMAIN (pbb)); + /* Map the iteration domain through the current scatter, and work + on the resulting set. */ + transdomain = isl_set_apply (isl_set_copy (pbb->domain), + isl_map_copy (pbb->transformed)); - ppl_Pointset_Powerset_C_Polyhedron_space_dimension (domain, &domain_dim); + /* Select the time_depth' dimension via an affine expression. */ + dc = isl_set_get_space (transdomain); + aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc)); + aff = isl_aff_set_coefficient_si (aff, isl_dim_in, time_depth, 1); - mpz_init (diff); - mpz_init (lb); - mpz_init (ub); - mpz_init (one); - mpz_set_si (one, 1); - - /* Compute the upper bound on the original iteration domain and add - that upper bound to the scattering. */ - ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron - (&sctr_ub, PBB_TRANSFORMED_SCATTERING (pbb)); - for (i = 0; i < (int) dim_iter_domain; i++) - { - ppl_Linear_Expression_t eq; - ppl_Constraint_t pc; - ppl_Constraint_System_t cs; - ppl_Polyhedron_t ph; - ppl_Pointset_Powerset_C_Polyhedron_t pph; - - ppl_new_Linear_Expression_with_dimension (&le, domain_dim); - ppl_set_coef (le, i, 1); - ppl_min_for_le_pointset (domain, le, lb); - ppl_max_for_le_pointset (domain, le, ub); - mpz_sub (diff, ub, lb); - mpz_add (diff, diff, one); - - ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim); - ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1); - ppl_set_inhomogeneous_gmp (eq, diff); - - ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL); - ppl_new_Constraint_System_from_Constraint (&cs, pc); - ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs); - ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph); - ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_ub, pph); - - ppl_delete_Linear_Expression (le); - ppl_delete_Linear_Expression (eq); - ppl_delete_Polyhedron (ph); - ppl_delete_Pointset_Powerset_C_Polyhedron (pph); - ppl_delete_Constraint (pc); - ppl_delete_Constraint_System (cs); - } + /* And find the min/max for that function. */ + /* XXX isl check results? */ + isl_set_min (transdomain, aff, &isllb); + isl_set_max (transdomain, aff, &islub); - /* Compute the lower bound on the original iteration domain and add - it to the scattering. */ - ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron - (&sctr_lb, PBB_TRANSFORMED_SCATTERING (pbb)); - for (i = 0; i < (int) dim_iter_domain; i++) - { - ppl_Linear_Expression_t eq; - ppl_Constraint_t pc; - ppl_Constraint_System_t cs; - ppl_Polyhedron_t ph; - ppl_Pointset_Powerset_C_Polyhedron_t pph; - - ppl_new_Linear_Expression_with_dimension (&le, domain_dim); - ppl_set_coef (le, i, 1); - ppl_min_for_le_pointset (domain, le, lb); - - ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim); - ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1); - ppl_set_inhomogeneous_gmp (eq, lb); - - ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL); - ppl_new_Constraint_System_from_Constraint (&cs, pc); - ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs); - ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph); - ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_lb, pph); - - ppl_delete_Linear_Expression (le); - ppl_delete_Linear_Expression (eq); - ppl_delete_Polyhedron (ph); - ppl_delete_Pointset_Powerset_C_Polyhedron (pph); - ppl_delete_Constraint (pc); - ppl_delete_Constraint_System (cs); - } + isl_int_sub (islub, islub, isllb); + isl_int_add_ui (islub, islub, 1); + isl_int_get_gmp (islub, res); - /* Extract the number of iterations. */ - ppl_new_Linear_Expression_with_dimension (&le, sctr_dim); - ppl_set_coef (le, time_depth, 1); - ppl_min_for_le_pointset (sctr_lb, le, lb); - ppl_max_for_le_pointset (sctr_ub, le, ub); - mpz_sub (res, ub, lb); - - mpz_clear (one); - mpz_clear (diff); - mpz_clear (lb); - mpz_clear (ub); - ppl_delete_Linear_Expression (le); - ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_ub); - ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_lb); - ppl_delete_Pointset_Powerset_C_Polyhedron (domain); + isl_int_clear (isllb); + isl_int_clear (islub); + isl_aff_free (aff); + isl_set_free (transdomain); } /* Translates LOOP to LST. */ @@ -1927,5 +1246,45 @@ cloog_checksum (scop_p scop ATTRIBUTE_UNUSED) #endif } +/* Reverse the loop around PBB at level DEPTH. */ + +isl_map * +reverse_loop_at_level (poly_bb_p pbb, int depth) +{ + unsigned i, depth_dim = psct_dynamic_dim (pbb, depth); + isl_space *d = isl_map_get_space (pbb->transformed); + isl_space *d1 = isl_space_range (d); + unsigned n = isl_space_dim (d1, isl_dim_out); + isl_space *d2 = isl_space_add_dims (d1, isl_dim_in, n); + isl_map *x = isl_map_universe (isl_space_copy (d2)); + isl_constraint *c = isl_equality_alloc (isl_local_space_from_space (d2)); + + for (i = 0; i < n; i++) + if (i != depth_dim) + x = isl_map_equate (x, isl_dim_in, i, isl_dim_out, i); + + c = isl_constraint_set_coefficient_si (c, isl_dim_in, depth_dim, 1); + c = isl_constraint_set_coefficient_si (c, isl_dim_out, depth_dim, 1); + x = isl_map_add_constraint (x, c); + return x; +} + +/* Reverse the loop at level DEPTH for all the PBBS. */ + +isl_union_map * +reverse_loop_for_pbbs (scop_p scop, VEC (poly_bb_p, heap) *pbbs, int depth) +{ + poly_bb_p pbb; + int i; + isl_space *space = isl_space_from_domain (isl_set_get_space (scop->context)); + isl_union_map *res = isl_union_map_empty (space); + + for (i = 0; VEC_iterate (poly_bb_p, pbbs, i, pbb); i++) + res = isl_union_map_add_map (res, reverse_loop_at_level (pbb, depth)); + + return res; +} + + #endif |