11debfc3dSmrg /* Data dependence analysis for Graphite.
2*8feb0f0bSmrg Copyright (C) 2009-2020 Free Software Foundation, Inc.
31debfc3dSmrg Contributed by Sebastian Pop <sebastian.pop@amd.com> and
41debfc3dSmrg Konrad Trifunovic <konrad.trifunovic@inria.fr>.
51debfc3dSmrg
61debfc3dSmrg This file is part of GCC.
71debfc3dSmrg
81debfc3dSmrg GCC is free software; you can redistribute it and/or modify
91debfc3dSmrg it under the terms of the GNU General Public License as published by
101debfc3dSmrg the Free Software Foundation; either version 3, or (at your option)
111debfc3dSmrg any later version.
121debfc3dSmrg
131debfc3dSmrg GCC is distributed in the hope that it will be useful,
141debfc3dSmrg but WITHOUT ANY WARRANTY; without even the implied warranty of
151debfc3dSmrg MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
161debfc3dSmrg GNU General Public License for more details.
171debfc3dSmrg
181debfc3dSmrg You should have received a copy of the GNU General Public License
191debfc3dSmrg along with GCC; see the file COPYING3. If not see
201debfc3dSmrg <http://www.gnu.org/licenses/>. */
211debfc3dSmrg
221debfc3dSmrg #define USES_ISL
231debfc3dSmrg
241debfc3dSmrg #include "config.h"
251debfc3dSmrg
261debfc3dSmrg #ifdef HAVE_isl
271debfc3dSmrg
281debfc3dSmrg #include "system.h"
291debfc3dSmrg #include "coretypes.h"
301debfc3dSmrg #include "backend.h"
311debfc3dSmrg #include "cfghooks.h"
321debfc3dSmrg #include "tree.h"
331debfc3dSmrg #include "gimple.h"
341debfc3dSmrg #include "fold-const.h"
351debfc3dSmrg #include "gimple-iterator.h"
361debfc3dSmrg #include "tree-ssa-loop.h"
371debfc3dSmrg #include "tree-pass.h"
381debfc3dSmrg #include "cfgloop.h"
391debfc3dSmrg #include "tree-data-ref.h"
401debfc3dSmrg #include "graphite.h"
411debfc3dSmrg
421debfc3dSmrg /* Add the constraints from the set S to the domain of MAP. */
431debfc3dSmrg
441debfc3dSmrg static isl_map *
constrain_domain(isl_map * map,isl_set * s)451debfc3dSmrg constrain_domain (isl_map *map, isl_set *s)
461debfc3dSmrg {
471debfc3dSmrg isl_space *d = isl_map_get_space (map);
481debfc3dSmrg isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
491debfc3dSmrg
501debfc3dSmrg s = isl_set_set_tuple_id (s, id);
511debfc3dSmrg isl_space_free (d);
521debfc3dSmrg return isl_map_coalesce (isl_map_intersect_domain (map, s));
531debfc3dSmrg }
541debfc3dSmrg
551debfc3dSmrg /* Constrain pdr->accesses with pdr->subscript_sizes and pbb->domain. */
561debfc3dSmrg
571debfc3dSmrg static isl_map *
add_pdr_constraints(poly_dr_p pdr,poly_bb_p pbb)581debfc3dSmrg add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
591debfc3dSmrg {
601debfc3dSmrg isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
611debfc3dSmrg isl_set_copy (pdr->subscript_sizes));
621debfc3dSmrg x = isl_map_coalesce (x);
631debfc3dSmrg return constrain_domain (x, isl_set_copy (pbb->domain));
641debfc3dSmrg }
651debfc3dSmrg
66a2dc1f3fSmrg /* Returns an isl description of all memory operations in SCOP. The memory
67a2dc1f3fSmrg reads are returned in READS and writes in MUST_WRITES and MAY_WRITES. */
681debfc3dSmrg
69a2dc1f3fSmrg static void
scop_get_reads_and_writes(scop_p scop,isl_union_map * & reads,isl_union_map * & must_writes,isl_union_map * & may_writes)70a2dc1f3fSmrg scop_get_reads_and_writes (scop_p scop, isl_union_map *&reads,
71a2dc1f3fSmrg isl_union_map *&must_writes,
72a2dc1f3fSmrg isl_union_map *&may_writes)
731debfc3dSmrg {
741debfc3dSmrg int i, j;
751debfc3dSmrg poly_bb_p pbb;
761debfc3dSmrg poly_dr_p pdr;
771debfc3dSmrg
781debfc3dSmrg FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
791debfc3dSmrg {
80a2dc1f3fSmrg FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) {
811debfc3dSmrg if (pdr_read_p (pdr))
821debfc3dSmrg {
831debfc3dSmrg if (dump_file)
841debfc3dSmrg {
851debfc3dSmrg fprintf (dump_file, "Adding read to depedence graph: ");
861debfc3dSmrg print_pdr (dump_file, pdr);
871debfc3dSmrg }
881debfc3dSmrg isl_union_map *um
891debfc3dSmrg = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
90a2dc1f3fSmrg reads = isl_union_map_union (reads, um);
911debfc3dSmrg if (dump_file)
921debfc3dSmrg {
931debfc3dSmrg fprintf (dump_file, "Reads depedence graph: ");
94a2dc1f3fSmrg print_isl_union_map (dump_file, reads);
951debfc3dSmrg }
961debfc3dSmrg }
97a2dc1f3fSmrg else if (pdr_write_p (pdr))
981debfc3dSmrg {
991debfc3dSmrg if (dump_file)
1001debfc3dSmrg {
1011debfc3dSmrg fprintf (dump_file, "Adding must write to depedence graph: ");
1021debfc3dSmrg print_pdr (dump_file, pdr);
1031debfc3dSmrg }
1041debfc3dSmrg isl_union_map *um
1051debfc3dSmrg = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
106a2dc1f3fSmrg must_writes = isl_union_map_union (must_writes, um);
1071debfc3dSmrg if (dump_file)
1081debfc3dSmrg {
1091debfc3dSmrg fprintf (dump_file, "Must writes depedence graph: ");
110a2dc1f3fSmrg print_isl_union_map (dump_file, must_writes);
1111debfc3dSmrg }
1121debfc3dSmrg }
113a2dc1f3fSmrg else if (pdr_may_write_p (pdr))
1141debfc3dSmrg {
1151debfc3dSmrg if (dump_file)
1161debfc3dSmrg {
1171debfc3dSmrg fprintf (dump_file, "Adding may write to depedence graph: ");
1181debfc3dSmrg print_pdr (dump_file, pdr);
1191debfc3dSmrg }
1201debfc3dSmrg isl_union_map *um
1211debfc3dSmrg = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
122a2dc1f3fSmrg may_writes = isl_union_map_union (may_writes, um);
1231debfc3dSmrg if (dump_file)
1241debfc3dSmrg {
1251debfc3dSmrg fprintf (dump_file, "May writes depedence graph: ");
126a2dc1f3fSmrg print_isl_union_map (dump_file, may_writes);
1271debfc3dSmrg }
1281debfc3dSmrg }
1291debfc3dSmrg }
130a2dc1f3fSmrg }
1311debfc3dSmrg }
1321debfc3dSmrg
1331debfc3dSmrg /* Helper function used on each MAP of a isl_union_map. Computes the
1341debfc3dSmrg maximal output dimension. */
1351debfc3dSmrg
1361debfc3dSmrg static isl_stat
max_number_of_out_dimensions(__isl_take isl_map * map,void * user)1371debfc3dSmrg max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
1381debfc3dSmrg {
1391debfc3dSmrg int global_max = *((int *) user);
1401debfc3dSmrg isl_space *space = isl_map_get_space (map);
1411debfc3dSmrg int nb_out = isl_space_dim (space, isl_dim_out);
1421debfc3dSmrg
1431debfc3dSmrg if (global_max < nb_out)
1441debfc3dSmrg *((int *) user) = nb_out;
1451debfc3dSmrg
1461debfc3dSmrg isl_map_free (map);
1471debfc3dSmrg isl_space_free (space);
1481debfc3dSmrg return isl_stat_ok;
1491debfc3dSmrg }
1501debfc3dSmrg
1511debfc3dSmrg /* Extends the output dimension of MAP to MAX dimensions. */
1521debfc3dSmrg
1531debfc3dSmrg static __isl_give isl_map *
extend_map(__isl_take isl_map * map,int max)1541debfc3dSmrg extend_map (__isl_take isl_map *map, int max)
1551debfc3dSmrg {
1561debfc3dSmrg isl_space *space = isl_map_get_space (map);
1571debfc3dSmrg int n = isl_space_dim (space, isl_dim_out);
1581debfc3dSmrg
1591debfc3dSmrg isl_space_free (space);
1601debfc3dSmrg return isl_map_add_dims (map, isl_dim_out, max - n);
1611debfc3dSmrg }
1621debfc3dSmrg
1631debfc3dSmrg /* Structure used to pass parameters to extend_schedule_1. */
1641debfc3dSmrg
1651debfc3dSmrg struct extend_schedule_str {
1661debfc3dSmrg int max;
1671debfc3dSmrg isl_union_map *umap;
1681debfc3dSmrg };
1691debfc3dSmrg
1701debfc3dSmrg /* Helper function for extend_schedule. */
1711debfc3dSmrg
1721debfc3dSmrg static isl_stat
extend_schedule_1(__isl_take isl_map * map,void * user)1731debfc3dSmrg extend_schedule_1 (__isl_take isl_map *map, void *user)
1741debfc3dSmrg {
1751debfc3dSmrg struct extend_schedule_str *str = (struct extend_schedule_str *) user;
1761debfc3dSmrg str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
1771debfc3dSmrg return isl_stat_ok;
1781debfc3dSmrg }
1791debfc3dSmrg
1801debfc3dSmrg /* Return a relation that has uniform output dimensions. */
1811debfc3dSmrg
1821debfc3dSmrg static __isl_give isl_union_map *
extend_schedule(__isl_take isl_union_map * x)1831debfc3dSmrg extend_schedule (__isl_take isl_union_map *x)
1841debfc3dSmrg {
1851debfc3dSmrg int max = 0;
1861debfc3dSmrg struct extend_schedule_str str;
1871debfc3dSmrg
1881debfc3dSmrg isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
1891debfc3dSmrg str.max = max;
1901debfc3dSmrg str.umap = isl_union_map_empty (isl_union_map_get_space (x));
1911debfc3dSmrg isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
1921debfc3dSmrg isl_union_map_free (x);
1931debfc3dSmrg return isl_union_map_coalesce (str.umap);
1941debfc3dSmrg }
1951debfc3dSmrg
1961debfc3dSmrg /* Applies SCHEDULE to the in and out dimensions of the dependences
1971debfc3dSmrg DEPS and return the resulting relation. */
1981debfc3dSmrg
1991debfc3dSmrg static isl_map *
apply_schedule_on_deps(__isl_keep isl_union_map * schedule,__isl_keep isl_union_map * deps)2001debfc3dSmrg apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
2011debfc3dSmrg __isl_keep isl_union_map *deps)
2021debfc3dSmrg {
2031debfc3dSmrg isl_union_map *trans = extend_schedule (isl_union_map_copy (schedule));
2041debfc3dSmrg isl_union_map *ux = isl_union_map_copy (deps);
2051debfc3dSmrg ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
2061debfc3dSmrg ux = isl_union_map_apply_range (ux, trans);
2071debfc3dSmrg ux = isl_union_map_coalesce (ux);
2081debfc3dSmrg
2091debfc3dSmrg if (!isl_union_map_is_empty (ux))
2101debfc3dSmrg return isl_map_from_union_map (ux);
2111debfc3dSmrg
2121debfc3dSmrg isl_union_map_free (ux);
2131debfc3dSmrg return NULL;
2141debfc3dSmrg }
2151debfc3dSmrg
2161debfc3dSmrg /* Return true when DEPS is non empty and the intersection of LEX with
2171debfc3dSmrg the DEPS transformed by SCHEDULE is non empty. LEX is the relation
2181debfc3dSmrg in which all the inputs before DEPTH occur at the same time as the
2191debfc3dSmrg output, and the input at DEPTH occurs before output. */
2201debfc3dSmrg
2211debfc3dSmrg bool
carries_deps(__isl_keep isl_union_map * schedule,__isl_keep isl_union_map * deps,int depth)2221debfc3dSmrg carries_deps (__isl_keep isl_union_map *schedule,
2231debfc3dSmrg __isl_keep isl_union_map *deps,
2241debfc3dSmrg int depth)
2251debfc3dSmrg {
2261debfc3dSmrg if (isl_union_map_is_empty (deps))
2271debfc3dSmrg return false;
2281debfc3dSmrg
2291debfc3dSmrg isl_map *x = apply_schedule_on_deps (schedule, deps);
2301debfc3dSmrg if (x == NULL)
2311debfc3dSmrg return false;
2321debfc3dSmrg
2331debfc3dSmrg isl_space *space = isl_map_get_space (x);
2341debfc3dSmrg isl_map *lex = isl_map_lex_le (isl_space_range (space));
2351debfc3dSmrg isl_constraint *ineq = isl_inequality_alloc
2361debfc3dSmrg (isl_local_space_from_space (isl_map_get_space (x)));
2371debfc3dSmrg
2381debfc3dSmrg for (int i = 0; i < depth - 1; i++)
2391debfc3dSmrg lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
2401debfc3dSmrg
2411debfc3dSmrg /* in + 1 <= out */
2421debfc3dSmrg ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
2431debfc3dSmrg ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
2441debfc3dSmrg ineq = isl_constraint_set_constant_si (ineq, -1);
2451debfc3dSmrg lex = isl_map_add_constraint (lex, ineq);
2461debfc3dSmrg lex = isl_map_coalesce (lex);
2471debfc3dSmrg x = isl_map_intersect (x, lex);
2481debfc3dSmrg bool res = !isl_map_is_empty (x);
2491debfc3dSmrg
2501debfc3dSmrg isl_map_free (x);
2511debfc3dSmrg return res;
2521debfc3dSmrg }
2531debfc3dSmrg
2541debfc3dSmrg /* Compute the dependence relations for the SCOP:
2551debfc3dSmrg RAW are read after write dependences,
2561debfc3dSmrg WAR are write after read dependences,
2571debfc3dSmrg WAW are write after write dependences. */
2581debfc3dSmrg
2591debfc3dSmrg void
scop_get_dependences(scop_p scop)2601debfc3dSmrg scop_get_dependences (scop_p scop)
2611debfc3dSmrg {
2621debfc3dSmrg if (scop->dependence)
2631debfc3dSmrg return;
2641debfc3dSmrg
265a2dc1f3fSmrg isl_space *space = isl_set_get_space (scop->param_context);
266a2dc1f3fSmrg isl_union_map *reads = isl_union_map_empty (isl_space_copy (space));
267a2dc1f3fSmrg isl_union_map *must_writes = isl_union_map_empty (isl_space_copy (space));
268a2dc1f3fSmrg isl_union_map *may_writes = isl_union_map_empty (space);
269a2dc1f3fSmrg scop_get_reads_and_writes (scop, reads, must_writes, may_writes);
2701debfc3dSmrg
2711debfc3dSmrg if (dump_file)
2721debfc3dSmrg {
2731debfc3dSmrg fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n");
2741debfc3dSmrg fprintf (dump_file, "Statements on the iteration domain are mapped to"
2751debfc3dSmrg " array references.\n");
2761debfc3dSmrg fprintf (dump_file, " To read the following data references:\n\n");
2771debfc3dSmrg fprintf (dump_file, " S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n");
2781debfc3dSmrg fprintf (dump_file, " S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n");
2791debfc3dSmrg
2801debfc3dSmrg fprintf (dump_file, " S_5[i0] is the dynamic instance of statement"
2811debfc3dSmrg " bb_5 in a loop that accesses all iterations 0 <= i0 <= 3.\n");
2821debfc3dSmrg fprintf (dump_file, " [1, i0] is a 'memref' with alias set 1"
2831debfc3dSmrg " and first subscript access i0.\n");
2841debfc3dSmrg fprintf (dump_file, " [106] is a 'scalar reference' which is the sum of"
2851debfc3dSmrg " SSA_NAME_VERSION 6"
2861debfc3dSmrg " and --param graphite-max-arrays-per-scop=100\n");
2871debfc3dSmrg fprintf (dump_file, "-----------------------\n\n");
2881debfc3dSmrg
2891debfc3dSmrg fprintf (dump_file, "data references (\n");
2901debfc3dSmrg fprintf (dump_file, " reads: ");
2911debfc3dSmrg print_isl_union_map (dump_file, reads);
2921debfc3dSmrg fprintf (dump_file, " must_writes: ");
2931debfc3dSmrg print_isl_union_map (dump_file, must_writes);
2941debfc3dSmrg fprintf (dump_file, " may_writes: ");
2951debfc3dSmrg print_isl_union_map (dump_file, may_writes);
2961debfc3dSmrg fprintf (dump_file, ")\n");
2971debfc3dSmrg }
2981debfc3dSmrg
2991debfc3dSmrg gcc_assert (scop->original_schedule);
3001debfc3dSmrg
3011debfc3dSmrg isl_union_access_info *ai;
3021debfc3dSmrg ai = isl_union_access_info_from_sink (isl_union_map_copy (reads));
3031debfc3dSmrg ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes));
3041debfc3dSmrg ai = isl_union_access_info_set_may_source (ai, may_writes);
3051debfc3dSmrg ai = isl_union_access_info_set_schedule
3061debfc3dSmrg (ai, isl_schedule_copy (scop->original_schedule));
3071debfc3dSmrg isl_union_flow *flow = isl_union_access_info_compute_flow (ai);
3081debfc3dSmrg isl_union_map *raw = isl_union_flow_get_must_dependence (flow);
3091debfc3dSmrg isl_union_flow_free (flow);
3101debfc3dSmrg
3111debfc3dSmrg ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes));
3121debfc3dSmrg ai = isl_union_access_info_set_must_source (ai, must_writes);
3131debfc3dSmrg ai = isl_union_access_info_set_may_source (ai, reads);
3141debfc3dSmrg ai = isl_union_access_info_set_schedule
3151debfc3dSmrg (ai, isl_schedule_copy (scop->original_schedule));
3161debfc3dSmrg flow = isl_union_access_info_compute_flow (ai);
3171debfc3dSmrg
3181debfc3dSmrg isl_union_map *waw = isl_union_flow_get_must_dependence (flow);
3191debfc3dSmrg isl_union_map *war = isl_union_flow_get_may_dependence (flow);
3201debfc3dSmrg war = isl_union_map_subtract (war, isl_union_map_copy (waw));
3211debfc3dSmrg isl_union_flow_free (flow);
3221debfc3dSmrg
3231debfc3dSmrg raw = isl_union_map_coalesce (raw);
3241debfc3dSmrg waw = isl_union_map_coalesce (waw);
3251debfc3dSmrg war = isl_union_map_coalesce (war);
3261debfc3dSmrg
3271debfc3dSmrg isl_union_map *dependences = raw;
3281debfc3dSmrg dependences = isl_union_map_union (dependences, war);
3291debfc3dSmrg dependences = isl_union_map_union (dependences, waw);
3301debfc3dSmrg dependences = isl_union_map_coalesce (dependences);
3311debfc3dSmrg
3321debfc3dSmrg if (dump_file)
3331debfc3dSmrg {
3341debfc3dSmrg fprintf (dump_file, "data dependences (\n");
3351debfc3dSmrg print_isl_union_map (dump_file, dependences);
3361debfc3dSmrg fprintf (dump_file, ")\n");
3371debfc3dSmrg }
3381debfc3dSmrg
3391debfc3dSmrg scop->dependence = dependences;
3401debfc3dSmrg }
3411debfc3dSmrg
3421debfc3dSmrg #endif /* HAVE_isl */
343