From 504fbc11f43fd20c33e5c44cc626f339f6fd8f8d Mon Sep 17 00:00:00 2001 From: Abderrazek Zaafrani Date: Sat, 7 Nov 2015 01:32:20 +0000 Subject: [PATCH] do not create unnecessary dimensions in scop scattering * graphite-sese-to-poly.c (build_pbb_scattering_polyhedrons): Remove. (build_pbb_minimal_scattering_polyhedrons): New. (build_scop_scattering): Remove. (build_scop_minimal_scattering): New. (build_scop_scattering): Call build_pbb_minimal_scattering_polyhedrons. (build_poly_scop): Call build_scop_minimal_scattering. From-SVN: r229909 --- gcc/ChangeLog | 9 ++ gcc/graphite-sese-to-poly.c | 190 ++++++++++++++++++++++++++---------- 2 files changed, 145 insertions(+), 54 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 552c51b2ceb..bac7eb87199 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,12 @@ +2015-11-06 Abderrazek Zaafrani + + * graphite-sese-to-poly.c (build_pbb_scattering_polyhedrons): Remove. + (build_pbb_minimal_scattering_polyhedrons): New. + (build_scop_scattering): Remove. + (build_scop_minimal_scattering): New. + (build_scop_scattering): Call build_pbb_minimal_scattering_polyhedrons. + (build_poly_scop): Call build_scop_minimal_scattering. + 2015-11-06 Jeff Law * cfg-flags.def (IGNORE): New edge flag. diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index fa33c50a533..394a281a97e 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -231,51 +231,78 @@ isl_id_for_pbb (scop_p s, poly_bb_p pbb) | 0 0 1 0 0 0 0 0 -5 = 0 */ static void -build_pbb_scattering_polyhedrons (isl_aff *static_sched, - poly_bb_p pbb) +build_pbb_minimal_scattering_polyhedrons (isl_aff *static_sched, poly_bb_p pbb, + int *sequence_dims, + int nb_sequence_dim) { - isl_val *val; + int local_dim = isl_set_dim (pbb->domain, isl_dim_set); + + /* Remove a sequence dimension if irrelevant to domain of current pbb. */ + int actual_nb_dim = 0; + for (int i = 0; i < nb_sequence_dim; i++) + if (sequence_dims[i] <= local_dim) + actual_nb_dim++; + + /* Build an array that combines sequence dimensions and loops dimensions info. + This is used later to compute the static scattering polyhedrons. */ + bool *sequence_and_loop_dims = NULL; + if (local_dim + actual_nb_dim > 0) + { + sequence_and_loop_dims = XNEWVEC (bool, local_dim + actual_nb_dim); - int scattering_dimensions = isl_set_dim (pbb->domain, isl_dim_set) * 2 + 1; + int i = 0, j = 0; + for (; i < local_dim; i++) + { + if (sequence_dims && sequence_dims[j] == i) + { + /* True for sequence dimension. */ + sequence_and_loop_dims[i + j] = true; + j++; + } + /* False for loop dimension. */ + sequence_and_loop_dims[i + j] = false; + } + /* Fake loops make things shifted by one. */ + if (sequence_dims && sequence_dims[j] == i) + sequence_and_loop_dims[i + j] = true; + } + int scattering_dimensions = local_dim + actual_nb_dim; isl_space *dc = isl_set_get_space (pbb->domain); - isl_space *dm = isl_space_add_dims (isl_space_from_domain (dc), - isl_dim_out, scattering_dimensions); + isl_space *dm = isl_space_add_dims (isl_space_from_domain (dc), isl_dim_out, + scattering_dimensions); pbb->schedule = isl_map_universe (dm); + int k = 0; for (int i = 0; i < scattering_dimensions; i++) { - /* Textual order inside this loop. */ - if ((i % 2) == 0) + if (!sequence_and_loop_dims[i]) { - isl_constraint *c = isl_equality_alloc - (isl_local_space_from_space (isl_map_get_space (pbb->schedule))); - - val = isl_aff_get_coefficient_val (static_sched, isl_dim_in, i / 2); - gcc_assert (val && isl_val_is_int (val)); - - val = isl_val_neg (val); - c = isl_constraint_set_constant_val (c, val); - c = isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1); - pbb->schedule = isl_map_add_constraint (pbb->schedule, c); - } - - /* Iterations of this loop. */ - else /* if ((i % 2) == 1) */ - { - int loop = (i - 1) / 2; - pbb->schedule = isl_map_equate (pbb->schedule, isl_dim_in, loop, + /* Iterations of this loop - loop dimension. */ + pbb->schedule = isl_map_equate (pbb->schedule, isl_dim_in, k, isl_dim_out, i); + k++; + continue; } + + /* Textual order inside this loop - sequence dimension. */ + isl_space *s = isl_map_get_space (pbb->schedule); + isl_local_space *ls = isl_local_space_from_space (s); + isl_constraint *c = isl_equality_alloc (ls); + isl_val *val = isl_aff_get_coefficient_val (static_sched, isl_dim_in, k); + gcc_assert (val && isl_val_is_int (val)); + val = isl_val_neg (val); + c = isl_constraint_set_constant_val (c, val); + c = isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1); + pbb->schedule = isl_map_add_constraint (pbb->schedule, c); } + XDELETEVEC (sequence_and_loop_dims); pbb->transformed = isl_map_copy (pbb->schedule); } -/* Build for BB the static schedule. - - The static schedule is a Dewey numbering of the abstract syntax - tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification +/* Build the static schedule for BB. This function minimizes the number of + dimensions used for pbb sequences. The following example informally defines the static schedule: @@ -283,40 +310,94 @@ build_pbb_scattering_polyhedrons (isl_aff *static_sched, for (i: ...) { for (j: ...) - { - B - C - } - + { + B + C + } + } + for (i: ...) + { for (k: ...) - { - D - E - } + { + D + E + } } F Static schedules for A to F: - DEPTH - 0 1 2 - A 0 - B 1 0 0 - C 1 0 1 - D 1 1 0 - E 1 1 1 - F 2 + A (0) + B (1 i0 i1 0) + C (1 i0 i1 1) + D (2 i0 i1 2) + E (2 i0 i1 3) + F (3) */ static void -build_scop_scattering (scop_p scop) +build_scop_minimal_scattering (scop_p scop) { gimple_poly_bb_p previous_gbb = NULL; - isl_space *dc = isl_set_get_space (scop->param_context); - isl_aff *static_sched; + int *temp_for_sequence_dims = NULL; + int i; + poly_bb_p pbb; + + /* Go through the pbbs to determine the minimum number of dimensions needed to + build the static schedule. */ + int nb_dims = 0; + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) + { + int dim = isl_set_dim (pbb->domain, isl_dim_set); + if (dim > nb_dims) + nb_dims = dim; + } + + /* One extra dimension for the outer fake loop. */ + nb_dims++; + temp_for_sequence_dims = XCNEWVEC (int, nb_dims); + /* Record the number of common loops for each dimension. */ + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) + { + gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); + int prefix = 0; + + if (previous_gbb) + { + prefix = nb_common_loops (scop->scop_info->region, previous_gbb, gbb); + temp_for_sequence_dims[prefix] += 1; + } + previous_gbb = gbb; + } + + /* Analyze the info in temp_for_sequence_dim and determine the minimal number + of sequence dimensions. A dimension that did not appear as common + dimension should not be considered as a sequence dimension. */ + int nb_sequence_params = 0; + for (i = 0; i < nb_dims; i++) + if (temp_for_sequence_dims[i] > 0) + nb_sequence_params++; + + int *sequence_dims = NULL; + if (nb_sequence_params > 0) + { + int j = 0; + sequence_dims = XNEWVEC (int, nb_sequence_params); + for (i = 0; i < nb_dims; i++) + if (temp_for_sequence_dims[i] > 0) + { + sequence_dims[j] = i; + j++; + } + } + + XDELETEVEC (temp_for_sequence_dims); + + isl_space *dc = isl_set_get_space (scop->param_context); dc = isl_space_add_dims (dc, isl_dim_set, number_of_loops (cfun)); - static_sched = isl_aff_zero_on_domain (isl_local_space_from_space (dc)); + isl_local_space *local_space = isl_local_space_from_space (dc); + isl_aff *static_sched = isl_aff_zero_on_domain (local_space); /* We have to start schedules at 0 on the first component and because we cannot compare_prefix_loops against a previous loop, @@ -324,8 +405,7 @@ build_scop_scattering (scop_p scop) incremented before copying. */ static_sched = isl_aff_add_coefficient_si (static_sched, isl_dim_in, 0, -1); - int i; - poly_bb_p pbb; + previous_gbb = NULL; FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) { gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); @@ -338,9 +418,11 @@ build_scop_scattering (scop_p scop) static_sched = isl_aff_add_coefficient_si (static_sched, isl_dim_in, prefix, 1); - build_pbb_scattering_polyhedrons (static_sched, pbb); + build_pbb_minimal_scattering_polyhedrons (static_sched, pbb, + sequence_dims, nb_sequence_params); } + XDELETEVEC (sequence_dims); isl_aff_free (static_sched); } @@ -1716,7 +1798,7 @@ build_poly_scop (scop_p scop) rewrite_cross_bb_scalar_deps_out_of_ssa (scop); build_scop_drs (scop); - build_scop_scattering (scop); + build_scop_minimal_scattering (scop); /* This SCoP has been translated to the polyhedral representation. */ -- 2.30.2