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;
+ mpz_t 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);
+ mpz_init (size);
+ mpz_set_si (size, 1);
+ mpz_init (sub_size);
+ mpz_set_si (sub_size, 1);
for (i = last - 1; i >= first; i--)
{
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);
+ mpz_mul (size, size, sub_size);
ppl_delete_Linear_Expression (le);
}
- value_clear (sub_size);
- value_clear (size);
+ mpz_clear (sub_size);
+ mpz_clear (size);
return res;
}
+/* 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
+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_Constraint_t new_cstr;
+ 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 (*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
- 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;
free (map);
}
- /* Add equalities:
- | t1 = t1'
- | ...
- | t_{depth-1} = t'_{depth-1}
- | t_{depth+1} = t'_{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 = psct_dynamic_dim (pbb, depth);
- for (i = 0; i < dim_sctr; 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);
- }
-
- /* 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);
+ build_partial_difference (&p1, time_depth, offset, dim_sctr);
/* Maximise the expression L2 - L1. */
{
ppl_max_for_le_pointset (p1, le, stride);
}
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ char *str;
+ void (*gmp_free) (void *, size_t);
+
+ fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d:",
+ pbb_index (pbb), PDR_ID (pdr), (int) depth);
+ str = mpz_get_str (0, 10, stride);
+ fprintf (dump_file, " %s ", str);
+ mp_get_memory_functions (NULL, NULL, &gmp_free);
+ (*gmp_free) (str, strlen (str) + 1);
+ }
+
ppl_delete_Pointset_Powerset_C_Polyhedron (p1);
ppl_delete_Pointset_Powerset_C_Polyhedron (p2);
ppl_delete_Linear_Expression (le);
}
-/* 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 (j = 0; VEC_iterate (lst_p, LST_SEQ (loop), j, l); j++)
+ if (LST_LOOP_P (l))
+ memory_strides_in_loop_1 (l, depth, strides);
+ else
+ for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (LST_PBB (l)), i, pdr); i++)
+ {
+ 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:
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 loop1, lst_p loop2)
{
- 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);
+ gcc_assert (loop1 && loop2
+ && LST_LOOP_P (loop1) && LST_LOOP_P (loop2)
+ && lst_depth (loop1) < lst_depth (loop2));
- for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
- {
- value_set_si (n, PDR_NB_REFS (pdr));
+ mpz_init (d1);
+ mpz_init (d2);
- 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 (loop1, lst_depth (loop1), d1);
+ memory_strides_in_loop (loop2, lst_depth (loop2), d2);
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;
}
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
-lst_interchange_profitable_p (lst_p lst, int depth1, int depth2)
-{
- if (!lst)
- return false;
-
- 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++)
- {
- 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 res;
- }
- else
- return pbb_interchange_profitable_p (depth1, depth2, LST_PBB (lst));
-}
-
/* Return true when the nest starting at LOOP1 and ending on LOOP2 is
perfect: i.e. there are no sequence of statements. */
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;
+ }
}
/* 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. */
+ interchange. */
static bool
-lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2,
- lst_p *before, lst_p *nest, lst_p *after)
+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;
- *before = NULL;
- *after = NULL;
- *nest = NULL;
+ lst_p before = NULL, nest = NULL, after = NULL;
- if (!lst_interchange_profitable_p (loop2, depth1, depth2))
+ if (!lst_interchange_profitable_p (loop1, loop2))
return false;
if (!lst_perfectly_nested_p (loop1, loop2))
- lst_perfect_nestify (loop1, loop2, before, nest, after);
+ 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)
+ if (before || nest || after)
{
transformed = lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop), loop1,
- *before, *nest, *after);
+ before, nest, after);
lst_update_scattering (transformed);
free_lst (transformed);
}
depth1, depth2);
/* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP. */
- lst_insert_in_sequence (*before, loop1, true);
- lst_insert_in_sequence (*after, loop1, false);
+ lst_insert_in_sequence (before, loop1, true);
+ lst_insert_in_sequence (after, loop1, false);
- if (*nest)
+ if (nest)
{
- lst_replace (loop1, *nest);
+ lst_replace (loop1, nest);
free_lst (loop1);
}
}
/* Undo the transform. */
+ free_lst (before);
+ free_lst (nest);
+ free_lst (after);
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. */
+/* 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, int *index)
+lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer,
+ lst_p inner_father)
{
- int i;
- lst_p l;
- lst_p before, nest, after;
- bool res;
-
- if (!lst || !LST_LOOP_P (lst))
- return false;
-
- 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)
- {
- res |= lst_do_interchange_1 (scop, after, index);
- (*index)++;
- }
-
- (*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. */
+ int inner;
+ lst_p loop1, loop2;
-static bool
-lst_do_interchange_1 (scop_p scop, lst_p loop, int *index)
-{
- int i;
- lst_p l;
- bool res = false;
+ gcc_assert (outer_father
+ && LST_LOOP_P (outer_father)
+ && LST_LOOP_P (VEC_index (lst_p, LST_SEQ (outer_father), outer))
+ && inner_father
+ && LST_LOOP_P (inner_father));
- if (!loop || !LST_LOOP_P (loop))
- return false;
+ loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer);
- for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l); i++)
- res |= lst_try_interchange (scop, loop, l, index);
+ for (inner = 0; VEC_iterate (lst_p, LST_SEQ (inner_father), inner, loop2); inner++)
+ if (LST_LOOP_P (loop2)
+ && (lst_try_interchange_loops (scop, loop1, loop2)
+ || lst_interchange_select_inner (scop, outer_father, outer, loop2)))
+ return true;
- return res;
+ return false;
}
/* 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. */
+ interchanged some 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 loop, int *index)
+lst_interchange_select_outer (scop_p scop, lst_p loop, int outer)
{
lst_p l;
bool res = false;
+ int i = 0;
+ lst_p father;
if (!loop || !LST_LOOP_P (loop))
return false;
- if (lst_depth (loop) >= 0)
- res = lst_do_interchange_1 (scop, loop, index);
+ father = LST_LOOP_FATHER (loop);
+ if (father)
+ {
+ while (lst_interchange_select_inner (scop, father, outer, loop))
+ {
+ res = true;
+ loop = VEC_index (lst_p, LST_SEQ (father), outer);
+ }
+ }
- while (VEC_iterate (lst_p, LST_SEQ (loop), *index, l))
- if (LST_LOOP_P (l))
- res |= lst_do_interchange (scop, l, index);
- else
- (*index)++;
+ if (LST_LOOP_P (loop))
+ for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l); i++)
+ if (LST_LOOP_P (l))
+ res |= lst_interchange_select_outer (scop, l, i);
- (*index)++;
return res;
}
bool
scop_do_interchange (scop_p scop)
{
- int i = 0;
- bool res = lst_do_interchange (scop, SCOP_TRANSFORMED_SCHEDULE (scop), &i);
+ bool res = lst_interchange_select_outer
+ (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop));
OSDN Git Service
