X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=gcc%2Fgraphite-interchange.c;h=7a51ca438212320ce5e39c1397de3f4cfce510e5;hb=abb226c954fadee4955160f0952e12296fc4a25e;hp=5107f91614f312b65edac2b94da58cc341cf01a9;hpb=67255edf95e35608b4d3f3b4a375203019d6b8c1;p=platform%2Fupstream%2Fgcc.git diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c index 5107f91..7a51ca4 100644 --- a/gcc/graphite-interchange.c +++ b/gcc/graphite-interchange.c @@ -1,7 +1,7 @@ /* Interchange heuristics and transform for loop interchange on polyhedral representation. - Copyright (C) 2009 Free Software Foundation, Inc. + Copyright (C) 2009-2015 Free Software Foundation, Inc. Contributed by Sebastian Pop and Harsha Jagasia . @@ -20,39 +20,58 @@ 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 . */ + #include "config.h" + +#ifdef HAVE_isl +#include +#include +#include +#include +#include +#include + +/* Since ISL-0.13, the extern is in val_gmp.h. */ +#if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus) +extern "C" { +#endif +#include +#if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus) +} +#endif +#endif + #include "system.h" #include "coretypes.h" -#include "tm.h" -#include "ggc.h" +#include "alias.h" +#include "symtab.h" +#include "options.h" #include "tree.h" -#include "rtl.h" -#include "output.h" +#include "fold-const.h" +#include "predict.h" +#include "tm.h" +#include "hard-reg-set.h" +#include "function.h" +#include "dominance.h" +#include "cfg.h" #include "basic-block.h" -#include "diagnostic.h" -#include "tree-flow.h" -#include "toplev.h" -#include "tree-dump.h" -#include "timevar.h" +#include "tree-ssa-alias.h" +#include "internal-fn.h" +#include "gimple-expr.h" +#include "gimple.h" +#include "gimple-iterator.h" +#include "tree-ssa-loop.h" +#include "dumpfile.h" #include "cfgloop.h" #include "tree-chrec.h" #include "tree-data-ref.h" #include "tree-scalar-evolution.h" -#include "tree-pass.h" -#include "domwalk.h" -#include "value-prof.h" -#include "pointer-set.h" -#include "gimple.h" -#include "params.h" - -#ifdef HAVE_cloog -#include "cloog/cloog.h" -#include "ppl_c.h" #include "sese.h" -#include "graphite-ppl.h" -#include "graphite.h" + +#ifdef HAVE_isl #include "graphite-poly.h" +/* XXX isl rewrite following comment */ /* Builds a linear expression, of dimension DIM, representing PDR's memory access: @@ -70,209 +89,232 @@ along with GCC; see the file COPYING3. If not see where the expression itself is: c_0 * s_0 + c_1 * s_1 + ... c_n * s_n. */ -static ppl_Linear_Expression_t -build_linearized_memory_access (ppl_dimension_type offset, poly_dr_p pdr) +static isl_constraint * +build_linearized_memory_access (isl_map *map, poly_dr_p pdr) { - ppl_Linear_Expression_t res; - ppl_Linear_Expression_t le; - ppl_dimension_type i; - ppl_dimension_type first = pdr_subscript_dim (pdr, 0); - ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr)); - Value size, sub_size; - graphite_dim_t dim = offset + pdr_dim (pdr); - - ppl_new_Linear_Expression_with_dimension (&res, dim); - - value_init (size); - value_set_si (size, 1); - value_init (sub_size); - value_set_si (sub_size, 1); - - for (i = last - 1; i >= first; i--) - { - ppl_set_coef_gmp (res, i + offset, size); + isl_constraint *res; + isl_local_space *ls = isl_local_space_from_space (isl_map_get_space (map)); + unsigned offset, nsubs; + int i; + isl_ctx *ctx; + + isl_val *size, *subsize, *size1; - ppl_new_Linear_Expression_with_dimension (&le, dim - offset); - ppl_set_coef (le, i, 1); - ppl_max_for_le_pointset (PDR_ACCESSES (pdr), le, sub_size); - value_multiply (size, size, sub_size); - ppl_delete_Linear_Expression (le); + res = isl_equality_alloc (ls); + ctx = isl_local_space_get_ctx (ls); + size = isl_val_int_from_ui (ctx, 1); + + nsubs = isl_set_dim (pdr->extent, isl_dim_set); + /* -1 for the already included L dimension. */ + offset = isl_map_dim (map, isl_dim_out) - 1 - nsubs; + res = isl_constraint_set_coefficient_si (res, isl_dim_out, offset + nsubs, -1); + /* Go through all subscripts from last to first. First dimension + is the alias set, ignore it. */ + for (i = nsubs - 1; i >= 1; i--) + { + isl_space *dc; + isl_aff *aff; + + size1 = isl_val_copy (size); + res = isl_constraint_set_coefficient_val (res, isl_dim_out, offset + i, size); + dc = isl_set_get_space (pdr->extent); + aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc)); + aff = isl_aff_set_coefficient_si (aff, isl_dim_in, i, 1); + subsize = isl_set_max_val (pdr->extent, aff); + isl_aff_free (aff); + size = isl_val_mul (size1, subsize); } - value_clear (sub_size); - value_clear (size); + isl_val_free (size); + return res; } /* Set STRIDE to the stride of PDR in memory by advancing by one in - time dimension DEPTH. */ + the loop at DEPTH. */ static void -memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr) +pdr_stride_in_loop (mpz_t stride, graphite_dim_t depth, poly_dr_p pdr) { - ppl_dimension_type time_depth; - ppl_Linear_Expression_t le, lma; - ppl_Constraint_t new_cstr; - ppl_dimension_type i, *map; - ppl_Pointset_Powerset_C_Polyhedron_t p1, p2, sctr; - graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr) + 1; poly_bb_p pbb = PDR_PBB (pdr); - ppl_dimension_type offset = pbb_nb_scattering_transform (pbb) - + pbb_nb_local_vars (pbb) - + pbb_dim_iter_domain (pbb); - ppl_dimension_type offsetg = offset + pbb_nb_params (pbb); - ppl_dimension_type dim_sctr = pbb_nb_scattering_transform (pbb) - + pbb_nb_local_vars (pbb); - ppl_dimension_type dim_L1 = offset + offsetg + 2 * nb_subscripts; - ppl_dimension_type dim_L2 = offset + offsetg + 2 * nb_subscripts + 1; - ppl_dimension_type new_dim = offset + offsetg + 2 * nb_subscripts + 2; - - /* The resulting polyhedron should have the following format: - T|I|T'|I'|G|S|S'|l1|l2 - where: - | T = t_1..t_{dim_sctr} - | I = i_1..i_{dim_iter_domain} - | T'= t'_1..t'_{dim_sctr} - | I'= i'_1..i'_{dim_iter_domain} - | G = g_1..g_{nb_params} - | S = s_1..s_{nb_subscripts} - | S'= s'_1..s'_{nb_subscripts} - | l1 and l2 are scalars. - - Some invariants: - offset = dim_sctr + dim_iter_domain + nb_local_vars - offsetg = dim_sctr + dim_iter_domain + nb_local_vars + nb_params. */ - - /* Construct the T|I|0|0|G|0|0|0|0 part. */ - { - ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron - (&sctr, PBB_TRANSFORMED_SCATTERING (pbb)); - ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed - (sctr, 2 * nb_subscripts + 2); - ppl_insert_dimensions_pointset (sctr, offset, offset); - } - - /* Construct the 0|I|0|0|G|S|0|0|0 part. */ - { - ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron - (&p1, PDR_ACCESSES (pdr)); - ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed - (p1, nb_subscripts + 2); - ppl_insert_dimensions_pointset (p1, 0, dim_sctr); - ppl_insert_dimensions_pointset (p1, offset, offset); - } - - /* Construct the 0|0|0|0|0|S|0|l1|0 part. */ - { - lma = build_linearized_memory_access (offset + dim_sctr, pdr); - ppl_set_coef (lma, dim_L1, -1); - ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL); - ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr); - ppl_delete_Linear_Expression (lma); - ppl_delete_Constraint (new_cstr); - } - - /* Now intersect all the parts to get the polyhedron P1: - T|I|0|0|G|0|0|0 |0 - 0|I|0|0|G|S|0|0 |0 - 0|0|0|0|0|S|0|l1|0 - ------------------ - T|I|0|0|G|S|0|l1|0. */ - - ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, sctr); - ppl_delete_Pointset_Powerset_C_Polyhedron (sctr); - - /* Build P2, which would have the following form: - 0|0|T'|I'|G|0|S'|0|l2 - - P2 is built, by remapping the P1 polyhedron: - T|I|0|0|G|S|0|l1|0 - - using the following mapping: - T->T' - I->I' - S->S' - l1->l2. */ - { - ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron - (&p2, p1); - - map = ppl_new_id_map (new_dim); - - /* TI -> T'I'. */ - for (i = 0; i < offset; i++) - ppl_interchange (map, i, i + offset); - - /* l1 -> l2. */ - ppl_interchange (map, dim_L1, dim_L2); - - /* S -> S'. */ - for (i = 0; i < nb_subscripts; i++) - ppl_interchange (map, offset + offsetg + i, - offset + offsetg + nb_subscripts + i); - - ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim); - free (map); - } + isl_map *map; + isl_set *set; + isl_aff *aff; + isl_space *dc; + isl_constraint *lma, *c; + isl_val *islstride; + graphite_dim_t time_depth; + unsigned offset, nt; + unsigned i; + /* XXX isl rewrite following comments. */ + /* Builds a partial difference equations and inserts them + into pointset powerset polyhedron P. Polyhedron is assumed + to have the format: T|I|T'|I'|G|S|S'|l1|l2. + + TIME_DEPTH is the time dimension w.r.t. which we are + differentiating. + OFFSET represents the number of dimensions between + columns t_{time_depth} and t'_{time_depth}. + DIM_SCTR is the number of scattering dimensions. It is + essentially the dimensionality of the T vector. + + The following equations are inserted into the polyhedron P: + | t_1 = t_1' + | ... + | t_{time_depth-1} = t'_{time_depth-1} + | t_{time_depth} = t'_{time_depth} + 1 + | t_{time_depth+1} = t'_{time_depth + 1} + | ... + | t_{dim_sctr} = t'_{dim_sctr}. */ + + /* Add the equality: t_{time_depth} = t'_{time_depth} + 1. + This is the core part of this alogrithm, since this + constraint asks for the memory access stride (difference) + between two consecutive points in time dimensions. */ /* Add equalities: | t1 = t1' | ... - | t_{depth-1} = t'_{depth-1} - | t_{depth+1} = t'_{depth+1} + | t_{time_depth-1} = t'_{time_depth-1} + | t_{time_depth+1} = t'_{time_depth+1} | ... | t_{dim_sctr} = t'_{dim_sctr} This means that all the time dimensions are equal except for - depth, where we will add t_{depth} = t'_{depth} + 1 in the next - step. */ - + time_depth, where the constraint is t_{depth} = t'_{depth} + 1 + step. More to this: we should be careful not to add equalities + to the 'coupled' dimensions, which happens when the one dimension + is stripmined dimension, and the other dimension corresponds + to the point loop inside stripmined dimension. */ + + /* pdr->accesses: [P1..nb_param,I1..nb_domain]->[a,S1..nb_subscript] + ??? [P] not used for PDRs? + pdr->extent: [a,S1..nb_subscript] + pbb->domain: [P1..nb_param,I1..nb_domain] + pbb->transformed: [P1..nb_param,I1..nb_domain]->[T1..Tnb_sctr] + [T] includes local vars (currently unused) + + First we create [P,I] -> [T,a,S]. */ + + map = isl_map_flat_range_product (isl_map_copy (pbb->transformed), + isl_map_copy (pdr->accesses)); + /* Add a dimension for L: [P,I] -> [T,a,S,L].*/ + map = isl_map_add_dims (map, isl_dim_out, 1); + /* Build a constraint for "lma[S] - L == 0", effectively calculating + L in terms of subscripts. */ + lma = build_linearized_memory_access (map, pdr); + /* And add it to the map, so we now have: + [P,I] -> [T,a,S,L] : lma([S]) == L. */ + map = isl_map_add_constraint (map, lma); + + /* Then we create [P,I,P',I'] -> [T,a,S,L,T',a',S',L']. */ + map = isl_map_flat_product (map, isl_map_copy (map)); + + /* Now add the equality T[time_depth] == T'[time_depth]+1. This will + force L' to be the linear address at T[time_depth] + 1. */ time_depth = psct_dynamic_dim (pbb, depth); - for (i = 0; i < dim_sctr; i++) + /* Length of [a,S] plus [L] ... */ + offset = 1 + isl_map_dim (pdr->accesses, isl_dim_out); + /* ... plus [T]. */ + offset += isl_map_dim (pbb->transformed, isl_dim_out); + + c = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (map))); + c = isl_constraint_set_coefficient_si (c, isl_dim_out, time_depth, 1); + c = isl_constraint_set_coefficient_si (c, isl_dim_out, + offset + time_depth, -1); + c = isl_constraint_set_constant_si (c, 1); + map = isl_map_add_constraint (map, c); + + /* Now we equate most of the T/T' elements (making PITaSL nearly + the same is (PITaSL)', except for one dimension, namely for 'depth' + (an index into [I]), after translating to index into [T]. Take care + to not produce an empty map, which indicates we wanted to equate + two dimensions that are already coupled via the above time_depth + dimension. Happens with strip mining where several scatter dimension + are interdependend. */ + /* Length of [T]. */ + nt = pbb_nb_scattering_transform (pbb) + pbb_nb_local_vars (pbb); + for (i = 0; i < nt; i++) if (i != time_depth) { - ppl_new_Linear_Expression_with_dimension (&le, new_dim); - ppl_set_coef (le, i, 1); - ppl_set_coef (le, i + offset, -1); - ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL); - ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr); - ppl_delete_Linear_Expression (le); - ppl_delete_Constraint (new_cstr); + isl_map *temp = isl_map_equate (isl_map_copy (map), + isl_dim_out, i, + isl_dim_out, offset + i); + if (isl_map_is_empty (temp)) + isl_map_free (temp); + else + { + isl_map_free (map); + map = temp; + } } - /* Add equality : t_{depth} = t'_{depth} + 1. - This is the core part of this alogrithm, since this - constraint asks for the memory access stride (difference) - between two consecutive points in time dimensions. */ - { - ppl_new_Linear_Expression_with_dimension (&le, new_dim); - ppl_set_coef (le, time_depth, 1); - ppl_set_coef (le, time_depth + offset, -1); - ppl_set_inhomogeneous (le, 1); - ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL); - ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr); - ppl_delete_Linear_Expression (le); - ppl_delete_Constraint (new_cstr); - } - - /* P1 = P1 inter P2. */ - ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2); - - /* Maximise the expression L2 - L1. */ - { - ppl_new_Linear_Expression_with_dimension (&le, new_dim); - ppl_set_coef (le, dim_L2, 1); - ppl_set_coef (le, dim_L1, -1); - ppl_max_for_le_pointset (p1, le, stride); - } - - ppl_delete_Pointset_Powerset_C_Polyhedron (p1); - ppl_delete_Pointset_Powerset_C_Polyhedron (p2); - ppl_delete_Linear_Expression (le); + /* Now maximize the expression L' - L. */ + set = isl_map_range (map); + dc = isl_set_get_space (set); + aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc)); + aff = isl_aff_set_coefficient_si (aff, isl_dim_in, offset - 1, -1); + aff = isl_aff_set_coefficient_si (aff, isl_dim_in, offset + offset - 1, 1); + islstride = isl_set_max_val (set, aff); + isl_val_get_num_gmp (islstride, stride); + isl_val_free (islstride); + isl_aff_free (aff); + isl_set_free (set); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + gmp_fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d: %Zd ", + pbb_index (pbb), PDR_ID (pdr), (int) depth, stride); + } } -/* Returns true when it is profitable to interchange time dimensions DEPTH1 - and DEPTH2 with DEPTH1 < DEPTH2 for PBB. +/* Sets STRIDES to the sum of all the strides of the data references + accessed in LOOP at DEPTH. */ + +static void +memory_strides_in_loop_1 (lst_p loop, graphite_dim_t depth, mpz_t strides) +{ + int i, j; + lst_p l; + poly_dr_p pdr; + mpz_t s, n; + + mpz_init (s); + mpz_init (n); + + FOR_EACH_VEC_ELT (LST_SEQ (loop), j, l) + if (LST_LOOP_P (l)) + memory_strides_in_loop_1 (l, depth, strides); + else + FOR_EACH_VEC_ELT (PBB_DRS (LST_PBB (l)), i, pdr) + { + pdr_stride_in_loop (s, depth, pdr); + mpz_set_si (n, PDR_NB_REFS (pdr)); + mpz_mul (s, s, n); + mpz_add (strides, strides, s); + } + + mpz_clear (s); + mpz_clear (n); +} + +/* Sets STRIDES to the sum of all the strides of the data references + accessed in LOOP at DEPTH. */ + +static void +memory_strides_in_loop (lst_p loop, graphite_dim_t depth, mpz_t strides) +{ + if (mpz_cmp_si (loop->memory_strides, -1) == 0) + { + mpz_set_si (strides, 0); + memory_strides_in_loop_1 (loop, depth, strides); + } + else + mpz_set (strides, loop->memory_strides); +} + +/* Return true when the interchange of loops LOOP1 and LOOP2 is + profitable. Example: @@ -353,42 +395,23 @@ memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr) profitable to interchange the loops at DEPTH1 and DEPTH2. */ static bool -pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2, - poly_bb_p pbb) +lst_interchange_profitable_p (lst_p nest, int depth1, int depth2) { - int i; - poly_dr_p pdr; - Value d1, d2, s, n; + mpz_t d1, d2; bool res; gcc_assert (depth1 < depth2); - value_init (d1); - value_set_si (d1, 0); - value_init (d2); - value_set_si (d2, 0); - value_init (s); - value_init (n); + mpz_init (d1); + mpz_init (d2); - for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++) - { - value_set_si (n, PDR_NB_REFS (pdr)); + memory_strides_in_loop (nest, depth1, d1); + memory_strides_in_loop (nest, depth2, d2); - memory_stride_in_loop (s, depth1, pdr); - value_multiply (s, s, n); - value_addto (d1, d1, s); + res = mpz_cmp (d1, d2) < 0; - memory_stride_in_loop (s, depth2, pdr); - value_multiply (s, s, n); - value_addto (d2, d2, s); - } - - res = value_lt (d1, d2); - - value_clear (d1); - value_clear (d2); - value_clear (s); - value_clear (n); + mpz_clear (d1); + mpz_clear (d2); return res; } @@ -401,23 +424,23 @@ static void pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb) { - ppl_dimension_type i, dim; - ppl_dimension_type *map; - ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb); - ppl_dimension_type dim1 = psct_dynamic_dim (pbb, depth1); - ppl_dimension_type dim2 = psct_dynamic_dim (pbb, depth2); - - ppl_Polyhedron_space_dimension (poly, &dim); - map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim); - - for (i = 0; i < dim; i++) - map[i] = i; - - map[dim1] = dim2; - map[dim2] = dim1; - - ppl_Polyhedron_map_space_dimensions (poly, map, dim); - free (map); + unsigned i; + unsigned dim1 = psct_dynamic_dim (pbb, depth1); + unsigned dim2 = psct_dynamic_dim (pbb, depth2); + 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 (d2); + + x = isl_map_equate (x, isl_dim_in, dim1, isl_dim_out, dim2); + x = isl_map_equate (x, isl_dim_in, dim2, isl_dim_out, dim1); + + for (i = 0; i < n; i++) + if (i != dim1 && i != dim2) + x = isl_map_equate (x, isl_dim_in, i, isl_dim_out, i); + + pbb->transformed = isl_map_apply_range (pbb->transformed, x); } /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all @@ -434,48 +457,75 @@ lst_apply_interchange (lst_p lst, int depth1, int depth2) int i; lst_p l; - for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) + FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l) lst_apply_interchange (l, depth1, depth2); } else pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst)); } -/* Return true when the interchange of loops at depths DEPTH1 and - DEPTH2 to all the statements below LST is profitable. */ +/* Return true when the nest starting at LOOP1 and ending on LOOP2 is + perfect: i.e. there are no sequence of statements. */ static bool -lst_interchange_profitable_p (lst_p lst, int depth1, int depth2) +lst_perfectly_nested_p (lst_p loop1, lst_p loop2) { - if (!lst) + if (loop1 == loop2) + return true; + + if (!LST_LOOP_P (loop1)) return false; - if (LST_LOOP_P (lst)) - { - int i; - lst_p l; - bool res = false; + return LST_SEQ (loop1).length () == 1 + && lst_perfectly_nested_p (LST_SEQ (loop1)[0], loop2); +} - for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) - { - bool profitable = lst_interchange_profitable_p (l, depth1, depth2); +/* Transform the loop nest between LOOP1 and LOOP2 into a perfect + nest. To continue the naming tradition, this function is called + after perfect_nestify. NEST is set to the perfectly nested loop + that is created. BEFORE/AFTER are set to the loops distributed + before/after the loop NEST. */ - if (profitable && !LST_LOOP_P (lst) - && dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - "Interchanging loops at depths %d and %d is profitable for stmt_%d.\n", - depth1, depth2, pbb_index (LST_PBB (lst))); +static void +lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before, + lst_p *nest, lst_p *after) +{ + poly_bb_p first, last; - res |= profitable; - } + gcc_assert (loop1 && loop2 + && loop1 != loop2 + && LST_LOOP_P (loop1) && LST_LOOP_P (loop2)); + + first = LST_PBB (lst_find_first_pbb (loop2)); + last = LST_PBB (lst_find_last_pbb (loop2)); + + *before = copy_lst (loop1); + *nest = copy_lst (loop1); + *after = copy_lst (loop1); - return res; + lst_remove_all_before_including_pbb (*before, first, false); + lst_remove_all_before_including_pbb (*after, last, true); + + lst_remove_all_before_excluding_pbb (*nest, first, true); + lst_remove_all_before_excluding_pbb (*nest, last, false); + + if (lst_empty_p (*before)) + { + free_lst (*before); + *before = NULL; + } + if (lst_empty_p (*after)) + { + free_lst (*after); + *after = NULL; + } + if (lst_empty_p (*nest)) + { + free_lst (*nest); + *nest = NULL; } - else - return pbb_interchange_profitable_p (depth1, depth2, LST_PBB (lst)); } - /* Try to interchange LOOP1 with LOOP2 for all the statements of the body of LOOP2. LOOP1 contains LOOP2. Return true if it did the interchange. */ @@ -485,12 +535,28 @@ lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2) { int depth1 = lst_depth (loop1); int depth2 = lst_depth (loop2); + lst_p transformed; + + lst_p before = NULL, nest = NULL, after = NULL; + + if (!lst_perfectly_nested_p (loop1, loop2)) + lst_perfect_nestify (loop1, loop2, &before, &nest, &after); if (!lst_interchange_profitable_p (loop2, depth1, depth2)) return false; lst_apply_interchange (loop2, depth1, depth2); + /* Sync the transformed LST information and the PBB scatterings + before using the scatterings in the data dependence analysis. */ + if (before || nest || after) + { + transformed = lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop), loop1, + before, nest, after); + lst_update_scattering (transformed); + free_lst (transformed); + } + if (graphite_legal_transform (scop)) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -498,87 +564,100 @@ lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2) "Loops at depths %d and %d will be interchanged.\n", depth1, depth2); + /* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP. */ + lst_insert_in_sequence (before, loop1, true); + lst_insert_in_sequence (after, loop1, false); + + if (nest) + { + lst_replace (loop1, nest); + free_lst (loop1); + } + return true; } /* Undo the transform. */ + free_lst (before); + free_lst (nest); + free_lst (after); lst_apply_interchange (loop2, depth2, depth1); return false; } -/* Try to interchange LOOP with all the loops contained in the body of - LST. Return true if it did interchanged some loops. */ +/* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged + with the loop OUTER in LST_SEQ (OUTER_FATHER). */ static bool -lst_try_interchange (scop_p scop, lst_p loop, lst_p lst) +lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer, + lst_p inner_father) { - if (!lst) - return false; + int inner; + lst_p loop1, loop2; - if (LST_LOOP_P (lst)) - { - int i; - lst_p l; - bool res = lst_try_interchange_loops (scop, loop, lst); + gcc_assert (outer_father + && LST_LOOP_P (outer_father) + && LST_LOOP_P (LST_SEQ (outer_father)[outer]) + && inner_father + && LST_LOOP_P (inner_father)); - for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) - res |= lst_try_interchange (scop, loop, l); + loop1 = LST_SEQ (outer_father)[outer]; - return res; - } + FOR_EACH_VEC_ELT (LST_SEQ (inner_father), inner, loop2) + if (LST_LOOP_P (loop2) + && (lst_try_interchange_loops (scop, loop1, loop2) + || lst_interchange_select_inner (scop, outer_father, outer, loop2))) + return true; return false; } -/* Interchanges all the loops of LST that are considered profitable to - interchange. Return true if it did interchanged some loops. */ +/* Interchanges all the loops of LOOP and the loops of its body that + are considered profitable to interchange. Return the number of + interchanged loops. OUTER is the index in LST_SEQ (LOOP) that + points to the next outer loop to be considered for interchange. */ -static bool -lst_do_interchange (scop_p scop, lst_p lst) +static int +lst_interchange_select_outer (scop_p scop, lst_p loop, int outer) { - if (!lst) - return false; - - if (LST_LOOP_P (lst)) - { - int i; - lst_p l; - bool res = false; - - if (lst_depth (lst) >= 0) - for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) - res |= lst_try_interchange (scop, lst, l); + lst_p l; + int res = 0; + int i = 0; + lst_p father; - for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) - res |= lst_do_interchange (scop, l); + if (!loop || !LST_LOOP_P (loop)) + return 0; - return res; + father = LST_LOOP_FATHER (loop); + if (father) + { + while (lst_interchange_select_inner (scop, father, outer, loop)) + { + res++; + loop = LST_SEQ (father)[outer]; + } } - return false; + if (LST_LOOP_P (loop)) + FOR_EACH_VEC_ELT (LST_SEQ (loop), i, l) + if (LST_LOOP_P (l)) + res += lst_interchange_select_outer (scop, l, i); + + return res; } -/* Interchanges all the loop depths that are considered profitable for SCOP. */ +/* Interchanges all the loop depths that are considered profitable for + SCOP. Return the number of interchanged loops. */ -bool +int scop_do_interchange (scop_p scop) { - bool transform_done = false; + int res = lst_interchange_select_outer + (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0); - store_scattering (scop); + lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop)); - transform_done = lst_do_interchange (scop, SCOP_TRANSFORMED_SCHEDULE (scop)); - - if (!transform_done) - return false; - - if (!graphite_legal_transform (scop)) - { - restore_scattering (scop); - return false; - } - - return transform_done; + return res; }