From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 106553 invoked by alias); 23 Nov 2015 23:20:31 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 106542 invoked by uid 89); 23 Nov 2015 23:20:30 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=1.5 required=5.0 tests=AWL,BAYES_50,KAM_LAZY_DOMAIN_SECURITY,TVD_RCVD_IP autolearn=no version=3.3.2 X-HELO: mailhost.sarc.sas Received: from 72-48-121-251.static.grandenetworks.net (HELO mailhost.sarc.sas) (72.48.121.251) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 23 Nov 2015 23:20:28 +0000 Received: from cc01.spa.sarc.sas (cc01.spa.sarc.sas [172.31.207.194]) by mailhost.sarc.sas (Postfix) with ESMTP id 699032E04C; Mon, 23 Nov 2015 17:20:27 -0600 (CST) Received: by cc01.spa.sarc.sas (Postfix, from userid 12626) id 505B64E242E; Mon, 23 Nov 2015 17:20:27 -0600 (CST) From: Sebastian Pop To: sebpop@gmail.com Cc: gcc-patches@gcc.gnu.org, hiraditya@msn.com, Sebastian Pop Subject: [PATCH] [graphite] fix PR68314: revert all patches touching the construction of the original schedule Date: Mon, 23 Nov 2015 23:39:00 -0000 Message-Id: <1448320825-19341-1-git-send-email-s.pop@samsung.com> X-SW-Source: 2015-11/txt/msg02808.txt.bz2 --- gcc/graphite-optimize-isl.c | 20 +--- gcc/graphite-poly.c | 2 - gcc/graphite-poly.h | 3 - gcc/graphite-sese-to-poly.c | 235 ++++++++++---------------------------------- 4 files changed, 58 insertions(+), 202 deletions(-) diff --git a/gcc/graphite-optimize-isl.c b/gcc/graphite-optimize-isl.c index 6ae224f..559afc4 100644 --- a/gcc/graphite-optimize-isl.c +++ b/gcc/graphite-optimize-isl.c @@ -442,23 +442,11 @@ optimize_isl (scop_p scop) #else isl_union_map *schedule_map = get_schedule_map (schedule); #endif + apply_schedule_map_to_scop (scop, schedule_map); - if (isl_union_map_is_equal (scop->original_schedule, schedule_map)) - { - if (dump_file && dump_flags) - fprintf (dump_file, "\nISL schedule same as original schedule\n"); - - isl_schedule_free (schedule); - isl_union_map_free (schedule_map); - return false; - } - else - { - apply_schedule_map_to_scop (scop, schedule_map); - isl_schedule_free (schedule); - isl_union_map_free (schedule_map); - return true; - } + isl_schedule_free (schedule); + isl_union_map_free (schedule_map); + return true; } #endif /* HAVE_isl */ diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index 187a3fa..c783fc3 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -306,7 +306,6 @@ new_scop (edge entry, edge exit) scop->must_waw_no_source = NULL; scop->may_waw_no_source = NULL; scop_set_region (scop, region); - scop->original_schedule = NULL; scop->pbbs.create (3); scop->drs.create (3); @@ -343,7 +342,6 @@ free_scop (scop_p scop) 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); - isl_union_map_free (scop->original_schedule); XDELETE (scop); } diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h index dec7fd6..d396d3f 100644 --- a/gcc/graphite-poly.h +++ b/gcc/graphite-poly.h @@ -417,9 +417,6 @@ struct scop isl_union_map *must_raw, *may_raw, *must_raw_no_source, *may_raw_no_source, *must_war, *may_war, *must_war_no_source, *may_war_no_source, *must_waw, *may_waw, *must_waw_no_source, *may_waw_no_source; - - /* Original schedule of the SCoP. */ - isl_union_map *original_schedule; }; extern scop_p new_scop (edge, edge); diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 65ff4e6..ec7248b 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -113,78 +113,51 @@ 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_minimal_scattering_polyhedrons (isl_aff *static_sched, poly_bb_p pbb, - int *sequence_dims, - int nb_sequence_dim) +build_pbb_scattering_polyhedrons (isl_aff *static_sched, + poly_bb_p pbb) { - 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); + isl_val *val; - 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 = isl_set_dim (pbb->domain, isl_dim_set) * 2 + 1; - 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++) { - if (!sequence_and_loop_dims[i]) + /* Textual order inside this loop. */ + if ((i % 2) == 0) { - /* Iterations of this loop - loop dimension. */ - pbb->schedule = isl_map_equate (pbb->schedule, isl_dim_in, k, - isl_dim_out, i); - k++; - continue; + 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); } - /* 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); + /* 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, + isl_dim_out, i); + } } - XDELETEVEC (sequence_and_loop_dims); pbb->transformed = isl_map_copy (pbb->schedule); } -/* Build the static schedule for BB. This function minimizes the number of - dimensions used for pbb sequences. +/* 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 The following example informally defines the static schedule: @@ -192,94 +165,40 @@ build_pbb_minimal_scattering_polyhedrons (isl_aff *static_sched, poly_bb_p pbb, for (i: ...) { for (j: ...) - { - B - C - } - } - for (i: ...) - { + { + B + C + } + for (k: ...) - { - D - E - } + { + D + E + } } F Static schedules for A to F: - A (0) - B (1 i0 i1 0) - C (1 i0 i1 1) - D (2 i0 i1 2) - E (2 i0 i1 3) - F (3) + DEPTH + 0 1 2 + A 0 + B 1 0 0 + C 1 0 1 + D 1 1 0 + E 1 1 1 + F 2 */ static void -build_scop_minimal_scattering (scop_p scop) +build_scop_scattering (scop_p scop) { gimple_poly_bb_p previous_gbb = NULL; - 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); + isl_aff *static_sched; + dc = isl_space_add_dims (dc, isl_dim_set, number_of_loops (cfun)); - isl_local_space *local_space = isl_local_space_from_space (dc); - isl_aff *static_sched = isl_aff_zero_on_domain (local_space); + static_sched = isl_aff_zero_on_domain (isl_local_space_from_space (dc)); /* We have to start schedules at 0 on the first component and because we cannot compare_prefix_loops against a previous loop, @@ -287,7 +206,8 @@ build_scop_minimal_scattering (scop_p scop) incremented before copying. */ static_sched = isl_aff_add_coefficient_si (static_sched, isl_dim_in, 0, -1); - previous_gbb = NULL; + int i; + poly_bb_p pbb; FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) { gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); @@ -300,58 +220,12 @@ build_scop_minimal_scattering (scop_p scop) static_sched = isl_aff_add_coefficient_si (static_sched, isl_dim_in, prefix, 1); - build_pbb_minimal_scattering_polyhedrons (static_sched, pbb, - sequence_dims, nb_sequence_params); + build_pbb_scattering_polyhedrons (static_sched, pbb); } - XDELETEVEC (sequence_dims); isl_aff_free (static_sched); } -/* Build the original schedule showing the orginal order of execution - of statement instances. - - The following example shows the original schedule: - - for (i: ...) - { - for (j: ...) - { - A - } - B - } - C - for (i: ...) - { - D - } - - Static schedules for A to D expressed in a union map: - { - S_A[i0, i1] -> [0, i0, 0, i1]; - S_B[i0] -> [0, i0, 1]; - S_C[] -> [1]; - S_D[i0] -> [2, i0, 0] - } -*/ - -static void -build_scop_original_schedule (scop_p scop) -{ - int i; - poly_bb_p pbb; - - isl_space *space = isl_set_get_space (scop->param_context); - isl_union_map *res = isl_union_map_empty (space); - - FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) - res = isl_union_map_add_map (res, isl_map_copy (pbb->schedule)); - - scop->original_schedule = res; -} - - static isl_pw_aff *extract_affine (scop_p, tree, __isl_take isl_space *space); /* Extract an affine expression from the chain of recurrence E. */ @@ -1244,8 +1118,7 @@ build_poly_scop (scop_p scop) return false; build_scop_drs (scop); - build_scop_minimal_scattering (scop); - build_scop_original_schedule (scop); + build_scop_scattering (scop); return true; } #endif /* HAVE_isl */ -- 1.9.1