diff options
Diffstat (limited to 'gcc/graphite-interchange.c')
| -rw-r--r-- | gcc/graphite-interchange.c | 627 |
1 files changed, 509 insertions, 118 deletions
diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c index 0a751d6336e..280a14e6d45 100644 --- a/gcc/graphite-interchange.c +++ b/gcc/graphite-interchange.c @@ -60,10 +60,18 @@ along with GCC; see the file COPYING3. If not see For an array A[10][20] with two subscript locations s0 and s1, the linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0 - corresponds to a memory stride of 20. */ + corresponds to a memory stride of 20. + + OFFSET is a number of dimensions to prepend before the + subscript dimensions: s_0, s_1, ..., s_n. + + Thus, the final linear expression has the following format: + 0 .. 0_{offset} | 0 .. 0_{nit} | 0 .. 0_{gd} | 0 | c_0 c_1 ... c_n + 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 (poly_dr_p pdr) +build_linearized_memory_access (ppl_dimension_type offset, poly_dr_p pdr) { ppl_Linear_Expression_t res; ppl_Linear_Expression_t le; @@ -71,7 +79,7 @@ build_linearized_memory_access (poly_dr_p pdr) 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 = pdr_dim (pdr); + graphite_dim_t dim = offset + pdr_dim (pdr); ppl_new_Linear_Expression_with_dimension (&res, dim); @@ -82,9 +90,9 @@ build_linearized_memory_access (poly_dr_p pdr) for (i = last - 1; i >= first; i--) { - ppl_set_coef_gmp (res, i, size); + ppl_set_coef_gmp (res, i + offset, size); - ppl_new_Linear_Expression_with_dimension (&le, dim); + 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); @@ -96,73 +104,259 @@ build_linearized_memory_access (poly_dr_p pdr) return res; } -/* Set STRIDE to the stride of PDR in memory by advancing by one in - loop DEPTH. */ +/* 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}. */ static void -memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr) +build_partial_difference (ppl_Pointset_Powerset_C_Polyhedron_t *p, + ppl_dimension_type time_depth, + ppl_dimension_type offset, + ppl_dimension_type dim_sctr) { - ppl_Linear_Expression_t le, lma; ppl_Constraint_t new_cstr; - ppl_Pointset_Powerset_C_Polyhedron_t p1, p2; - graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr); - ppl_dimension_type i, *map; - ppl_dimension_type dim = pdr_dim (pdr); - ppl_dimension_type dim_i = pdr_iterator_dim (pdr, depth); - ppl_dimension_type dim_k = dim; - ppl_dimension_type dim_L1 = dim + nb_subscripts + 1; - ppl_dimension_type dim_L2 = dim + nb_subscripts + 2; - ppl_dimension_type new_dim = dim + nb_subscripts + 3; - - /* Add new dimensions to the polyhedron corresponding to - k, s0', s1',..., L1, and L2. These new variables are at - dimensions dim, dim + 1,... of the polyhedron P1 respectively. */ - 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 + 3); - - lma = build_linearized_memory_access (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); - - /* Build P2. */ - ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron - (&p2, p1); - map = ppl_new_id_map (new_dim); - ppl_interchange (map, dim_L1, dim_L2); - ppl_interchange (map, dim_i, dim_k); - for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++) - ppl_interchange (map, pdr_subscript_dim (pdr, i), dim + i + 1); - ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim); - free (map); - - /* Add constraint k = i + 1. */ - ppl_new_Linear_Expression_with_dimension (&le, new_dim); - ppl_set_coef (le, dim_i, 1); - ppl_set_coef (le, dim_k, -1); + ppl_Linear_Expression_t le; + ppl_dimension_type i; + ppl_dimension_type dim; + ppl_Pointset_Powerset_C_Polyhedron_t temp; + + /* 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. */ + + ppl_Pointset_Powerset_C_Polyhedron_space_dimension (*p, &dim); + ppl_new_Linear_Expression_with_dimension (&le, 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_Pointset_Powerset_C_Polyhedron_add_constraint (*p, new_cstr); ppl_delete_Linear_Expression (le); ppl_delete_Constraint (new_cstr); + /* Add equalities: + | t1 = t1' + | ... + | 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 + time_depth, where the constraint is t_{depth} = t'_{depth} + 1 + step. More to this: we should be carefull 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. */ + + ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&temp, *p); + + for (i = 0; i < dim_sctr; i++) + if (i != time_depth) + { + ppl_new_Linear_Expression_with_dimension (&le, 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 (temp, new_cstr); + + if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp)) + { + ppl_delete_Pointset_Powerset_C_Polyhedron (temp); + ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&temp, *p); + } + else + ppl_Pointset_Powerset_C_Polyhedron_add_constraint (*p, new_cstr); + ppl_delete_Linear_Expression (le); + ppl_delete_Constraint (new_cstr); + } + + ppl_delete_Pointset_Powerset_C_Polyhedron (temp); +} + + +/* Set STRIDE to the stride of PDR in memory by advancing by one in + the loop at DEPTH. */ + +static void +memory_stride_in_loop (Value 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); + } + + time_depth = psct_dynamic_dim (pbb, depth); + /* P1 = P1 inter P2. */ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2); - ppl_delete_Pointset_Powerset_C_Polyhedron (p2); + build_partial_difference (&p1, time_depth, offset, dim_sctr); /* 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_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); + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d:", + pbb_index (pbb), PDR_ID (pdr), (int) depth); + value_print (dump_file, " %s ", stride); + } + + ppl_delete_Pointset_Powerset_C_Polyhedron (p1); + ppl_delete_Pointset_Powerset_C_Polyhedron (p2); ppl_delete_Linear_Expression (le); } +/* Sets STRIDES to the sum of all the strides of the data references accessed */ + +static void +memory_strides_in_loop_depth (poly_bb_p pbb, graphite_dim_t depth, Value strides) +{ + int i; + poly_dr_p pdr; + Value s, n; + + value_set_si (strides, 0); + value_init (s); + value_init (n); + + for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++) + { + value_set_si (n, PDR_NB_REFS (pdr)); -/* Returns true when it is profitable to interchange loop at DEPTH1 - and loop at DEPTH2 with DEPTH1 < DEPTH2 for PBB. + memory_stride_in_loop (s, depth, pdr); + value_multiply (s, s, n); + value_addto (strides, strides, s); + } + + value_clear (s); + value_clear (n); +} + +/* Returns true when it is profitable to interchange time dimensions DEPTH1 + and DEPTH2 with DEPTH1 < DEPTH2 for PBB. Example: @@ -197,9 +391,13 @@ memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr) | i j N a s0 s1 1 | 0 0 0 0 100 1 0 + TODO: the shown format is not valid as it does not show the fact + that the iteration domain "i j" is transformed using the scattering. + Next, to measure the impact of iterating once in loop "i", we build a maximization problem: first, we add to DR accesses the dimensions - k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: polyhedron P1. + k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: this is the polyhedron P1. + L1 and L2 are the linearized memory access functions. | i j N a s0 s1 k s2 s3 L1 L2 D1 1 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5 @@ -212,7 +410,7 @@ memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr) | 0 0 0 0 100 1 0 0 0 -1 0 0 0 = 0 L1 = 100 * s0 + s1 Then, we generate the polyhedron P2 by interchanging the dimensions - (s0, s2), (s1, s3), (L1, L2), (i0, i) + (s0, s2), (s1, s3), (L1, L2), (k, i) | i j N a s0 s1 k s2 s3 L1 L2 D1 1 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5 @@ -230,7 +428,7 @@ memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr) and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)". - For determining the impact of one iteration on loop "j", we + Similarly, to determine the impact of one iteration on loop "j", we interchange (k, j), we add "k = j + 1", and we compute D2 the maximal value of the difference. @@ -242,39 +440,21 @@ static bool pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb) { - int i; - poly_dr_p pdr; - Value d1, d2, s, n; + Value 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); - for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++) - { - value_set_si (n, PDR_NB_REFS (pdr)); - - memory_stride_in_loop (s, depth1, pdr); - value_multiply (s, s, n); - value_addto (d1, d1, s); - - memory_stride_in_loop (s, depth2, pdr); - value_multiply (s, s, n); - value_addto (d2, d2, s); - } + memory_strides_in_loop_depth (pbb, depth1, d1); + memory_strides_in_loop_depth (pbb, depth2, d2); res = value_lt (d1, d2); value_clear (d1); value_clear (d2); - value_clear (s); - value_clear (n); return res; } @@ -284,13 +464,14 @@ pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2, scattering. */ static void -pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb) +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_iterator_dim (pbb, depth1); - ppl_dimension_type dim2 = psct_iterator_dim (pbb, depth2); + 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); @@ -305,62 +486,272 @@ pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, poly_ free (map); } -/* Interchanges all the loop depths that are considered profitable for PBB. */ +/* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all + the statements below LST. */ + +static void +lst_apply_interchange (lst_p lst, int depth1, int depth2) +{ + if (!lst) + return; + + if (LST_LOOP_P (lst)) + { + int i; + lst_p l; + + for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) + 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. */ static bool -pbb_do_interchange (poly_bb_p pbb, scop_p scop) +lst_interchange_profitable_p (lst_p lst, int depth1, int depth2) { - graphite_dim_t i, j; - bool transform_done = false; + if (!lst) + return false; - for (i = 0; i < pbb_dim_iter_domain (pbb); i++) - for (j = i + 1; j < pbb_dim_iter_domain (pbb); j++) - if (pbb_interchange_profitable_p (i, j, pbb)) + if (LST_LOOP_P (lst)) + { + int i; + lst_p l; + bool res = false; + + for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) { - pbb_interchange_loop_depths (i, j, pbb); - - if (graphite_legal_transform (scop)) - { - transform_done = true; - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - "PBB %d: loops at depths %d and %d will be interchanged.\n", - GBB_BB (PBB_BLACK_BOX (pbb))->index, (int) i, (int) j); - } - else - /* Undo the transform. */ - pbb_interchange_loop_depths (j, i, pbb); + bool profitable = lst_interchange_profitable_p (l, depth1, depth2); + + 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))); + + res |= profitable; } - return transform_done; + return res; + } + else + return pbb_interchange_profitable_p (depth1, depth2, LST_PBB (lst)); } -/* Interchanges all the loop depths that are considered profitable for SCOP. */ +/* Return true when the nest starting at LOOP1 and ending on LOOP2 is + perfect: i.e. there are no sequence of statements. */ -bool -scop_do_interchange (scop_p scop) +static bool +lst_perfectly_nested_p (lst_p loop1, lst_p loop2) { - int i; - poly_bb_p pbb; - bool transform_done = false; + if (loop1 == loop2) + return true; - store_scattering (scop); + if (!LST_LOOP_P (loop1)) + return false; + + return VEC_length (lst_p, LST_SEQ (loop1)) == 1 + && lst_perfectly_nested_p (VEC_index (lst_p, LST_SEQ (loop1), 0), loop2); +} + +/* 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. */ + +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; + + 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); + + 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); +} + +/* 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. CREATED_LOOP_BEFORE/CREATED_LOOP_AFTER are set to + true if the loop distribution created a loop before/after LOOP1. */ + +static bool +lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2, + lst_p *before, lst_p *nest, lst_p *after) +{ + int depth1 = lst_depth (loop1); + int depth2 = lst_depth (loop2); + lst_p transformed; + + *before = NULL; + *after = NULL; + *nest = NULL; + + if (!lst_interchange_profitable_p (loop2, depth1, depth2)) + return false; - for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) - transform_done |= pbb_do_interchange (pbb, scop); + if (!lst_perfectly_nested_p (loop1, loop2)) + lst_perfect_nestify (loop1, loop2, before, nest, after); + + 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)) + fprintf (dump_file, + "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. */ + lst_apply_interchange (loop2, depth2, depth1); + *before = NULL; + *after = NULL; + *nest = NULL; + return false; +} + +static bool lst_do_interchange_1 (scop_p, lst_p, int *); + +/* Try to interchange LOOP with all the loops contained in the body of + LST. Return true if it did interchanged some loops. INDEX points + to the next element to be processed by lst_do_interchange. */ + +static bool +lst_try_interchange (scop_p scop, lst_p loop, lst_p lst, int *index) +{ + int i; + lst_p l; + lst_p before, nest, after; + bool res; - if (!transform_done) + if (!lst || !LST_LOOP_P (lst)) return false; - if (!graphite_legal_transform (scop)) + res = lst_try_interchange_loops (scop, loop, lst, &before, &nest, &after); + + if (before) + { + res |= lst_do_interchange_1 (scop, before, index); + (*index)++; + } + + if (nest) + res |= lst_do_interchange_1 (scop, nest, index); + else + for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) + res |= lst_try_interchange (scop, loop, l, index); + + if (after) { - restore_scattering (scop); - return false; + res |= lst_do_interchange_1 (scop, after, index); + (*index)++; } - return transform_done; + (*index)++; + return res; +} + +/* Interchanges all the loops of LOOP that are considered profitable + to interchange. Return true if it did interchanged some loops. + INDEX points to the next element to be processed by + lst_do_interchange. */ + +static bool +lst_do_interchange_1 (scop_p scop, lst_p loop, int *index) +{ + int i; + lst_p l; + bool res = false; + + if (!loop || !LST_LOOP_P (loop)) + return false; + + for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l); i++) + res |= lst_try_interchange (scop, loop, l, index); + + return res; +} + +/* Interchanges all the loops of LOOP and the loops of its body that + are considered profitable to interchange. Return true if it did + interchanged some loops. INDEX points to the next element to be + processed in the LST_SEQ (LOOP) vector. */ + +static bool +lst_do_interchange (scop_p scop, lst_p loop, int *index) +{ + lst_p l; + bool res = false; + + if (!loop || !LST_LOOP_P (loop)) + return false; + + if (lst_depth (loop) >= 0) + res = lst_do_interchange_1 (scop, loop, index); + + while (VEC_iterate (lst_p, LST_SEQ (loop), *index, l)) + if (LST_LOOP_P (l)) + res |= lst_do_interchange (scop, l, index); + else + (*index)++; + + (*index)++; + return res; +} + +/* Interchanges all the loop depths that are considered profitable for SCOP. */ + +bool +scop_do_interchange (scop_p scop) +{ + int i = 0; + bool res = lst_do_interchange (scop, SCOP_TRANSFORMED_SCHEDULE (scop), &i); + + lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop)); + + return res; } + #endif |