Daily bump.
[official-gcc.git] / gcc / graphite-dependences.c
blob4ed9d00b2fd0abfb5c518482923cd30baed80f52
1 /* Data dependence analysis for Graphite.
2 Copyright (C) 2009-2017 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4 Konrad Trifunovic <konrad.trifunovic@inria.fr>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #define USES_ISL
24 #include "config.h"
26 #ifdef HAVE_isl
28 #include "system.h"
29 #include "coretypes.h"
30 #include "backend.h"
31 #include "cfghooks.h"
32 #include "tree.h"
33 #include "gimple.h"
34 #include "fold-const.h"
35 #include "gimple-iterator.h"
36 #include "tree-ssa-loop.h"
37 #include "tree-pass.h"
38 #include "cfgloop.h"
39 #include "tree-data-ref.h"
40 #include "graphite.h"
42 /* Add the constraints from the set S to the domain of MAP. */
44 static isl_map *
45 constrain_domain (isl_map *map, isl_set *s)
47 isl_space *d = isl_map_get_space (map);
48 isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
50 s = isl_set_set_tuple_id (s, id);
51 isl_space_free (d);
52 return isl_map_coalesce (isl_map_intersect_domain (map, s));
55 /* Constrain pdr->accesses with pdr->subscript_sizes and pbb->domain. */
57 static isl_map *
58 add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
60 isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
61 isl_set_copy (pdr->subscript_sizes));
62 x = isl_map_coalesce (x);
63 return constrain_domain (x, isl_set_copy (pbb->domain));
66 /* Returns all the memory reads in SCOP. */
68 static isl_union_map *
69 scop_get_reads (scop_p scop)
71 int i, j;
72 poly_bb_p pbb;
73 poly_dr_p pdr;
74 isl_space *space = isl_set_get_space (scop->param_context);
75 isl_union_map *res = isl_union_map_empty (space);
77 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
79 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
80 if (pdr_read_p (pdr))
82 if (dump_file)
84 fprintf (dump_file, "Adding read to depedence graph: ");
85 print_pdr (dump_file, pdr);
87 isl_union_map *um
88 = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
89 res = isl_union_map_union (res, um);
90 if (dump_file)
92 fprintf (dump_file, "Reads depedence graph: ");
93 print_isl_union_map (dump_file, res);
98 return isl_union_map_coalesce (res);
101 /* Returns all the memory must writes in SCOP. */
103 static isl_union_map *
104 scop_get_must_writes (scop_p scop)
106 int i, j;
107 poly_bb_p pbb;
108 poly_dr_p pdr;
109 isl_space *space = isl_set_get_space (scop->param_context);
110 isl_union_map *res = isl_union_map_empty (space);
112 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
114 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
115 if (pdr_write_p (pdr))
117 if (dump_file)
119 fprintf (dump_file, "Adding must write to depedence graph: ");
120 print_pdr (dump_file, pdr);
122 isl_union_map *um
123 = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
124 res = isl_union_map_union (res, um);
125 if (dump_file)
127 fprintf (dump_file, "Must writes depedence graph: ");
128 print_isl_union_map (dump_file, res);
133 return isl_union_map_coalesce (res);
136 /* Returns all the memory may writes in SCOP. */
138 static isl_union_map *
139 scop_get_may_writes (scop_p scop)
141 int i, j;
142 poly_bb_p pbb;
143 poly_dr_p pdr;
144 isl_space *space = isl_set_get_space (scop->param_context);
145 isl_union_map *res = isl_union_map_empty (space);
147 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
149 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
150 if (pdr_may_write_p (pdr))
152 if (dump_file)
154 fprintf (dump_file, "Adding may write to depedence graph: ");
155 print_pdr (dump_file, pdr);
157 isl_union_map *um
158 = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
159 res = isl_union_map_union (res, um);
160 if (dump_file)
162 fprintf (dump_file, "May writes depedence graph: ");
163 print_isl_union_map (dump_file, res);
168 return isl_union_map_coalesce (res);
171 /* Helper function used on each MAP of a isl_union_map. Computes the
172 maximal output dimension. */
174 static isl_stat
175 max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
177 int global_max = *((int *) user);
178 isl_space *space = isl_map_get_space (map);
179 int nb_out = isl_space_dim (space, isl_dim_out);
181 if (global_max < nb_out)
182 *((int *) user) = nb_out;
184 isl_map_free (map);
185 isl_space_free (space);
186 return isl_stat_ok;
189 /* Extends the output dimension of MAP to MAX dimensions. */
191 static __isl_give isl_map *
192 extend_map (__isl_take isl_map *map, int max)
194 isl_space *space = isl_map_get_space (map);
195 int n = isl_space_dim (space, isl_dim_out);
197 isl_space_free (space);
198 return isl_map_add_dims (map, isl_dim_out, max - n);
201 /* Structure used to pass parameters to extend_schedule_1. */
203 struct extend_schedule_str {
204 int max;
205 isl_union_map *umap;
208 /* Helper function for extend_schedule. */
210 static isl_stat
211 extend_schedule_1 (__isl_take isl_map *map, void *user)
213 struct extend_schedule_str *str = (struct extend_schedule_str *) user;
214 str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
215 return isl_stat_ok;
218 /* Return a relation that has uniform output dimensions. */
220 static __isl_give isl_union_map *
221 extend_schedule (__isl_take isl_union_map *x)
223 int max = 0;
224 struct extend_schedule_str str;
226 isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
227 str.max = max;
228 str.umap = isl_union_map_empty (isl_union_map_get_space (x));
229 isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
230 isl_union_map_free (x);
231 return isl_union_map_coalesce (str.umap);
234 /* Applies SCHEDULE to the in and out dimensions of the dependences
235 DEPS and return the resulting relation. */
237 static isl_map *
238 apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
239 __isl_keep isl_union_map *deps)
241 isl_union_map *trans = extend_schedule (isl_union_map_copy (schedule));
242 isl_union_map *ux = isl_union_map_copy (deps);
243 ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
244 ux = isl_union_map_apply_range (ux, trans);
245 ux = isl_union_map_coalesce (ux);
247 if (!isl_union_map_is_empty (ux))
248 return isl_map_from_union_map (ux);
250 isl_union_map_free (ux);
251 return NULL;
254 /* Return true when DEPS is non empty and the intersection of LEX with
255 the DEPS transformed by SCHEDULE is non empty. LEX is the relation
256 in which all the inputs before DEPTH occur at the same time as the
257 output, and the input at DEPTH occurs before output. */
259 bool
260 carries_deps (__isl_keep isl_union_map *schedule,
261 __isl_keep isl_union_map *deps,
262 int depth)
264 if (isl_union_map_is_empty (deps))
265 return false;
267 isl_map *x = apply_schedule_on_deps (schedule, deps);
268 if (x == NULL)
269 return false;
271 isl_space *space = isl_map_get_space (x);
272 isl_map *lex = isl_map_lex_le (isl_space_range (space));
273 isl_constraint *ineq = isl_inequality_alloc
274 (isl_local_space_from_space (isl_map_get_space (x)));
276 for (int i = 0; i < depth - 1; i++)
277 lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
279 /* in + 1 <= out */
280 ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
281 ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
282 ineq = isl_constraint_set_constant_si (ineq, -1);
283 lex = isl_map_add_constraint (lex, ineq);
284 lex = isl_map_coalesce (lex);
285 x = isl_map_intersect (x, lex);
286 bool res = !isl_map_is_empty (x);
288 isl_map_free (x);
289 return res;
292 /* Compute the dependence relations for the SCOP:
293 RAW are read after write dependences,
294 WAR are write after read dependences,
295 WAW are write after write dependences. */
297 void
298 scop_get_dependences (scop_p scop)
300 if (scop->dependence)
301 return;
303 isl_union_map *reads = scop_get_reads (scop);
304 isl_union_map *must_writes = scop_get_must_writes (scop);
305 isl_union_map *may_writes = scop_get_may_writes (scop);
307 if (dump_file)
309 fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n");
310 fprintf (dump_file, "Statements on the iteration domain are mapped to"
311 " array references.\n");
312 fprintf (dump_file, " To read the following data references:\n\n");
313 fprintf (dump_file, " S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n");
314 fprintf (dump_file, " S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n");
316 fprintf (dump_file, " S_5[i0] is the dynamic instance of statement"
317 " bb_5 in a loop that accesses all iterations 0 <= i0 <= 3.\n");
318 fprintf (dump_file, " [1, i0] is a 'memref' with alias set 1"
319 " and first subscript access i0.\n");
320 fprintf (dump_file, " [106] is a 'scalar reference' which is the sum of"
321 " SSA_NAME_VERSION 6"
322 " and --param graphite-max-arrays-per-scop=100\n");
323 fprintf (dump_file, "-----------------------\n\n");
325 fprintf (dump_file, "data references (\n");
326 fprintf (dump_file, " reads: ");
327 print_isl_union_map (dump_file, reads);
328 fprintf (dump_file, " must_writes: ");
329 print_isl_union_map (dump_file, must_writes);
330 fprintf (dump_file, " may_writes: ");
331 print_isl_union_map (dump_file, may_writes);
332 fprintf (dump_file, ")\n");
335 gcc_assert (scop->original_schedule);
337 isl_union_access_info *ai;
338 ai = isl_union_access_info_from_sink (isl_union_map_copy (reads));
339 ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes));
340 ai = isl_union_access_info_set_may_source (ai, may_writes);
341 ai = isl_union_access_info_set_schedule
342 (ai, isl_schedule_copy (scop->original_schedule));
343 isl_union_flow *flow = isl_union_access_info_compute_flow (ai);
344 isl_union_map *raw = isl_union_flow_get_must_dependence (flow);
345 isl_union_flow_free (flow);
347 ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes));
348 ai = isl_union_access_info_set_must_source (ai, must_writes);
349 ai = isl_union_access_info_set_may_source (ai, reads);
350 ai = isl_union_access_info_set_schedule
351 (ai, isl_schedule_copy (scop->original_schedule));
352 flow = isl_union_access_info_compute_flow (ai);
354 isl_union_map *waw = isl_union_flow_get_must_dependence (flow);
355 isl_union_map *war = isl_union_flow_get_may_dependence (flow);
356 war = isl_union_map_subtract (war, isl_union_map_copy (waw));
357 isl_union_flow_free (flow);
359 raw = isl_union_map_coalesce (raw);
360 waw = isl_union_map_coalesce (waw);
361 war = isl_union_map_coalesce (war);
363 isl_union_map *dependences = raw;
364 dependences = isl_union_map_union (dependences, war);
365 dependences = isl_union_map_union (dependences, waw);
366 dependences = isl_union_map_coalesce (dependences);
368 if (dump_file)
370 fprintf (dump_file, "data dependences (\n");
371 print_isl_union_map (dump_file, dependences);
372 fprintf (dump_file, ")\n");
375 scop->dependence = dependences;
378 #endif /* HAVE_isl */