/* 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 <sebastian.pop@amd.com> and
Harsha Jagasia <harsha.jagasia@amd.com>.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
+
#include "config.h"
+
+#ifdef HAVE_isl
+#include <isl/aff.h>
+#include <isl/set.h>
+#include <isl/map.h>
+#include <isl/union_map.h>
+#include <isl/ilp.h>
+#include <isl/val.h>
+
+/* 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 <isl/val_gmp.h>
+#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"
-/* Returns the subscript dimension defined by CSTR in PDR. */
+/* XXX isl rewrite following comment */
+/* Builds a linear expression, of dimension DIM, representing PDR's
+ memory access:
-static ppl_dimension_type
-compute_subscript (poly_dr_p pdr, ppl_const_Constraint_t cstr)
-{
- graphite_dim_t i;
- ppl_Linear_Expression_t expr;
- ppl_Coefficient_t coef;
- Value val;
+ L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
- value_init (val);
- ppl_new_Coefficient (&coef);
+ 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.
- for (i = 0; i < pdr_nb_subscripts (pdr); i++)
- {
- ppl_dimension_type sub_dim = pdr_subscript_dim (pdr, i);
+ OFFSET is a number of dimensions to prepend before the
+ subscript dimensions: s_0, s_1, ..., s_n.
- ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
- ppl_Linear_Expression_coefficient (expr, sub_dim, coef);
- ppl_delete_Linear_Expression (expr);
- ppl_Coefficient_to_mpz_t (coef, val);
+ 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. */
- if (value_notzero_p (val))
- {
- gcc_assert (value_one_p (val)
- || value_mone_p (val));
+static isl_constraint *
+build_linearized_memory_access (isl_map *map, poly_dr_p pdr)
+{
+ 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;
- value_clear (val);
- ppl_delete_Coefficient (coef);
- return sub_dim;
- }
+ isl_val *size, *subsize, *size1;
+
+ 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);
}
- gcc_unreachable ();
- return 0;
+ isl_val_free (size);
+
+ return res;
}
+/* Set STRIDE to the stride of PDR in memory by advancing by one in
+ the loop at DEPTH. */
+
static void
-compute_array_size_cstr (ppl_dimension_type sub_dim, Value res,
- ppl_const_Constraint_t cstr)
+pdr_stride_in_loop (mpz_t stride, graphite_dim_t depth, poly_dr_p pdr)
{
- ppl_Linear_Expression_t expr;
- ppl_Coefficient_t coef;
- Value val;
+ poly_bb_p pbb = PDR_PBB (pdr);
+ 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_{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 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);
+ /* 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)
+ {
+ 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;
+ }
+ }
+
+ /* 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);
+ }
+}
- value_init (val);
- ppl_new_Coefficient (&coef);
- ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
- ppl_Linear_Expression_coefficient (expr, sub_dim, coef);
- ppl_Coefficient_to_mpz_t (coef, val);
+/* Sets STRIDES to the sum of all the strides of the data references
+ accessed in LOOP at DEPTH. */
- value_set_si (res, 0);
+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;
- if (value_notzero_p (val))
- {
- gcc_assert (value_one_p (val) || value_mone_p (val));
- ppl_Linear_Expression_inhomogeneous_term (expr, coef);
- ppl_Coefficient_to_mpz_t (coef, res);
- value_absolute (res, res);
- }
+ mpz_init (s);
+ mpz_init (n);
- value_clear (val);
- ppl_delete_Coefficient (coef);
- ppl_delete_Linear_Expression (expr);
+ 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);
}
-/* Returns in ARRAY_SIZE the size in bytes of the array PDR for the
- subscript at dimension SUB_DIM. */
+/* Sets STRIDES to the sum of all the strides of the data references
+ accessed in LOOP at DEPTH. */
static void
-compute_array_size_poly (poly_dr_p pdr, ppl_dimension_type sub_dim, Value array_size,
- ppl_const_Polyhedron_t ph)
+memory_strides_in_loop (lst_p loop, graphite_dim_t depth, mpz_t strides)
{
- ppl_const_Constraint_System_t pcs;
- ppl_Constraint_System_const_iterator_t cit, cend;
- ppl_const_Constraint_t cstr;
- Value val;
- Value res;
-
- if (sub_dim >= pdr_subscript_dim (pdr, pdr_nb_subscripts (pdr)))
+ if (mpz_cmp_si (loop->memory_strides, -1) == 0)
{
- value_set_si (array_size, 1);
- return;
+ 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:
+
+ | int a[100][100];
+ |
+ | int
+ | foo (int N)
+ | {
+ | int j;
+ | int i;
+ |
+ | for (i = 0; i < N; i++)
+ | for (j = 0; j < N; j++)
+ | a[j][2 * i] += 1;
+ |
+ | return a[N][12];
+ | }
+
+ The data access A[j][i] is described like this:
+
+ | i j N a s0 s1 1
+ | 0 0 0 1 0 0 -5 = 0
+ | 0 -1 0 0 1 0 0 = 0
+ |-2 0 0 0 0 1 0 = 0
+ | 0 0 0 0 1 0 0 >= 0
+ | 0 0 0 0 0 1 0 >= 0
+ | 0 0 0 0 -1 0 100 >= 0
+ | 0 0 0 0 0 -1 100 >= 0
+
+ The linearized memory access L to A[100][100] is:
+
+ | 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: 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
+ | 0 -1 0 0 1 0 0 0 0 0 0 0 0 = 0 s0 = j
+ |-2 0 0 0 0 1 0 0 0 0 0 0 0 = 0 s1 = 2 * i
+ | 0 0 0 0 1 0 0 0 0 0 0 0 0 >= 0
+ | 0 0 0 0 0 1 0 0 0 0 0 0 0 >= 0
+ | 0 0 0 0 -1 0 0 0 0 0 0 0 100 >= 0
+ | 0 0 0 0 0 -1 0 0 0 0 0 0 100 >= 0
+ | 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), (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
+ | 0 -1 0 0 0 0 0 1 0 0 0 0 0 = 0 s2 = j
+ | 0 0 0 0 0 0 -2 0 1 0 0 0 0 = 0 s3 = 2 * k
+ | 0 0 0 0 0 0 0 1 0 0 0 0 0 >= 0
+ | 0 0 0 0 0 0 0 0 1 0 0 0 0 >= 0
+ | 0 0 0 0 0 0 0 -1 0 0 0 0 100 >= 0
+ | 0 0 0 0 0 0 0 0 -1 0 0 0 100 >= 0
+ | 0 0 0 0 0 0 0 100 1 0 -1 0 0 = 0 L2 = 100 * s2 + s3
+
+ then we add to P2 the equality k = i + 1:
+
+ |-1 0 0 0 0 0 1 0 0 0 0 0 -1 = 0 k = i + 1
+
+ and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
+
+ 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.
+
+ Finally, the profitability test is D1 < D2: if in the outer loop
+ the strides are smaller than in the inner loop, then it is
+ profitable to interchange the loops at DEPTH1 and DEPTH2. */
- value_init (val);
- value_init (res);
+static bool
+lst_interchange_profitable_p (lst_p nest, int depth1, int depth2)
+{
+ mpz_t d1, d2;
+ bool res;
- value_set_si (res, 0);
+ gcc_assert (depth1 < depth2);
- ppl_Polyhedron_get_constraints (ph, &pcs);
- ppl_new_Constraint_System_const_iterator (&cit);
- ppl_new_Constraint_System_const_iterator (&cend);
-
- for (ppl_Constraint_System_begin (pcs, cit),
- ppl_Constraint_System_end (pcs, cend);
- !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
- ppl_Constraint_System_const_iterator_increment (cit))
- {
- ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
+ mpz_init (d1);
+ mpz_init (d2);
- if (ppl_Constraint_type (cstr) == PPL_CONSTRAINT_TYPE_EQUAL)
- continue;
+ memory_strides_in_loop (nest, depth1, d1);
+ memory_strides_in_loop (nest, depth2, d2);
- compute_array_size_cstr (sub_dim, val, cstr);
- value_max (res, res, val);
- }
+ res = mpz_cmp (d1, d2) < 0;
- compute_array_size_poly (pdr, sub_dim + 1, val, ph);
- value_multiply (array_size, res, val);
+ mpz_clear (d1);
+ mpz_clear (d2);
- value_clear (res);
- value_clear (val);
+ return res;
}
-/* Initializes ARRAY_SIZE, the size in bytes of the array for the
- subscript at dimension SUB_DIM in PDR. */
+/* Interchanges the loops at DEPTH1 and DEPTH2 of the original
+ scattering and assigns the resulting polyhedron to the transformed
+ scattering. */
static void
-compute_array_size (poly_dr_p pdr, ppl_dimension_type sub_dim, Value array_size)
+pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2,
+ poly_bb_p pbb)
{
- ppl_Pointset_Powerset_C_Polyhedron_t data_container = PDR_ACCESSES (pdr);
- ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
- Value val;
+ 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);
+}
- value_set_si (array_size, 1);
- if (sub_dim >= pdr_subscript_dim (pdr, pdr_nb_subscripts (pdr)))
- return;
+/* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
+ the statements below LST. */
- value_init (val);
- ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
- ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
+static void
+lst_apply_interchange (lst_p lst, int depth1, int depth2)
+{
+ if (!lst)
+ return;
- for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (data_container, it),
- ppl_Pointset_Powerset_C_Polyhedron_iterator_end (data_container, end);
- !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
- ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
+ if (LST_LOOP_P (lst))
{
- ppl_const_Polyhedron_t ph;
+ int i;
+ lst_p l;
- ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
- compute_array_size_poly (pdr, sub_dim, val, ph);
- value_max (array_size, array_size, val);
+ FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l)
+ lst_apply_interchange (l, depth1, depth2);
}
-
- value_clear (val);
- ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
- ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
+ else
+ pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
}
-/* Computes ACCESS_STRIDES, the sum of all the strides of PDR at
- LOOP_DEPTH. */
+/* Return true when the nest starting at LOOP1 and ending on LOOP2 is
+ perfect: i.e. there are no sequence of statements. */
-static void
-gather_access_strides_poly (poly_dr_p pdr, ppl_const_Polyhedron_t ph,
- ppl_dimension_type loop_dim, Value res)
+static bool
+lst_perfectly_nested_p (lst_p loop1, lst_p loop2)
{
- ppl_const_Constraint_System_t pcs;
- ppl_Constraint_System_const_iterator_t cit, cend;
- ppl_const_Constraint_t cstr;
- ppl_Linear_Expression_t expr;
- ppl_Coefficient_t coef;
- Value stride;
- Value array_size;
-
- value_init (array_size);
- value_init (stride);
- ppl_new_Coefficient (&coef);
- value_set_si (res, 0);
-
- ppl_Polyhedron_get_constraints (ph, &pcs);
- ppl_new_Constraint_System_const_iterator (&cit);
- ppl_new_Constraint_System_const_iterator (&cend);
-
- for (ppl_Constraint_System_begin (pcs, cit),
- ppl_Constraint_System_end (pcs, cend);
- !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
- ppl_Constraint_System_const_iterator_increment (cit))
- {
- ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
- ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
- ppl_Linear_Expression_coefficient (expr, loop_dim, coef);
- ppl_delete_Linear_Expression (expr);
- ppl_Coefficient_to_mpz_t (coef, stride);
-
- if (value_zero_p (stride))
- continue;
-
- value_absolute (stride, stride);
- compute_array_size (pdr, compute_subscript (pdr, cstr), array_size);
- value_multiply (stride, stride, array_size);
- value_addto (res, res, stride);
- }
+ if (loop1 == loop2)
+ return true;
- value_clear (array_size);
- value_clear (stride);
- ppl_delete_Coefficient (coef);
- ppl_delete_Constraint_System_const_iterator (cit);
- ppl_delete_Constraint_System_const_iterator (cend);
+ if (!LST_LOOP_P (loop1))
+ return false;
+
+ return LST_SEQ (loop1).length () == 1
+ && lst_perfectly_nested_p (LST_SEQ (loop1)[0], loop2);
}
-/* Computes ACCESS_STRIDES, the sum of all the strides of PDR at
- LOOP_DEPTH. */
+/* 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
-gather_access_strides (poly_dr_p pdr, graphite_dim_t loop_depth,
- Value access_strides)
+lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before,
+ lst_p *nest, lst_p *after)
{
- ppl_dimension_type loop_dim = pdr_iterator_dim (pdr, loop_depth);
+ poly_bb_p first, last;
- ppl_Pointset_Powerset_C_Polyhedron_t accesses = PDR_ACCESSES (pdr);
- ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
- Value res;
+ gcc_assert (loop1 && loop2
+ && loop1 != loop2
+ && LST_LOOP_P (loop1) && LST_LOOP_P (loop2));
- value_init (res);
- ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
- ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
+ first = LST_PBB (lst_find_first_pbb (loop2));
+ last = LST_PBB (lst_find_last_pbb (loop2));
- for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (accesses, it),
- ppl_Pointset_Powerset_C_Polyhedron_iterator_end (accesses, end);
- !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
- ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
- {
- ppl_const_Polyhedron_t ph;
+ *before = copy_lst (loop1);
+ *nest = copy_lst (loop1);
+ *after = copy_lst (loop1);
- ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
- gather_access_strides_poly (pdr, ph, loop_dim, res);
- value_addto (access_strides, access_strides, 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);
- value_clear (res);
- ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
- ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
+ 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;
+ }
}
-/* Returns true when it is profitable to interchange loop at depth1
- and loop at depth2 with depth1 < depth2 for the polyhedral black
- box PBB. */
+/* 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. */
static bool
-pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb)
+lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
{
- int i;
- poly_dr_p pdr;
- Value access_strides1, access_strides2;
- bool res;
+ int depth1 = lst_depth (loop1);
+ int depth2 = lst_depth (loop2);
+ lst_p transformed;
- gcc_assert (depth1 < depth2);
+ lst_p before = NULL, nest = NULL, after = NULL;
+
+ if (!lst_perfectly_nested_p (loop1, loop2))
+ lst_perfect_nestify (loop1, loop2, &before, &nest, &after);
- value_init (access_strides1);
- value_init (access_strides2);
+ if (!lst_interchange_profitable_p (loop2, depth1, depth2))
+ return false;
- value_set_si (access_strides1, 0);
- value_set_si (access_strides2, 0);
+ lst_apply_interchange (loop2, depth1, depth2);
- for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
+ /* Sync the transformed LST information and the PBB scatterings
+ before using the scatterings in the data dependence analysis. */
+ if (before || nest || after)
{
- gather_access_strides (pdr, depth1, access_strides1);
- gather_access_strides (pdr, depth2, access_strides2);
+ transformed = lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop), loop1,
+ before, nest, after);
+ lst_update_scattering (transformed);
+ free_lst (transformed);
}
- res = value_lt (access_strides1, access_strides2);
+ 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);
- value_clear (access_strides1);
- value_clear (access_strides2);
+ /* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP. */
+ lst_insert_in_sequence (before, loop1, true);
+ lst_insert_in_sequence (after, loop1, false);
- return res;
+ 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;
}
-/* Interchanges the loops at DEPTH1 and DEPTH2 of the original
- scattering and assigns the resulting polyhedron to the transformed
- scattering. */
+/* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged
+ with the loop OUTER in LST_SEQ (OUTER_FATHER). */
-static void
-pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb)
+static bool
+lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer,
+ lst_p inner_father)
{
- 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);
+ int inner;
+ lst_p loop1, loop2;
- ppl_Polyhedron_space_dimension (poly, &dim);
- map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
+ 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; i < dim; i++)
- map[i] = i;
+ loop1 = LST_SEQ (outer_father)[outer];
- map[dim1] = dim2;
- map[dim2] = dim1;
+ 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;
- ppl_Polyhedron_map_space_dimensions (poly, map, dim);
- free (map);
+ return false;
}
-/* Interchanges all the loop depths that are considered profitable for PBB. */
+/* 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
-pbb_do_interchange (poly_bb_p pbb, scop_p scop)
+static int
+lst_interchange_select_outer (scop_p scop, lst_p loop, int outer)
{
- graphite_dim_t i, j;
- bool transform_done = false;
+ lst_p l;
+ int res = 0;
+ int i = 0;
+ lst_p father;
+
+ if (!loop || !LST_LOOP_P (loop))
+ return 0;
- 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))
+ father = LST_LOOP_FATHER (loop);
+ if (father)
+ {
+ while (lst_interchange_select_inner (scop, father, outer, loop))
{
- 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);
+ res++;
+ loop = LST_SEQ (father)[outer];
}
+ }
+
+ 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 transform_done;
+ 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)
{
- int i;
- poly_bb_p pbb;
- bool transform_done = false;
-
- store_scattering (scop);
-
- for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
- transform_done |= pbb_do_interchange (pbb, scop);
+ int res = lst_interchange_select_outer
+ (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
- if (!transform_done)
- return false;
-
- if (!graphite_legal_transform (scop))
- {
- restore_scattering (scop);
- return false;
- }
+ lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop));
- return transform_done;
+ return res;
}
+
#endif