* g++.dg/cpp/ucn-1.C: Fix typo.
[official-gcc.git] / gcc / graphite-dependences.c
blobaef29acfb3ab7f594113722b917a1f13a35e6681
1 /* Data dependence analysis for Graphite.
2 Copyright (C) 2009-2015 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 #include "config.h"
24 #ifdef HAVE_isl
25 /* Workaround for GMP 5.1.3 bug, see PR56019. */
26 #include <stddef.h>
28 #include <isl/constraint.h>
29 #include <isl/set.h>
30 #include <isl/map.h>
31 #include <isl/union_map.h>
32 #include <isl/flow.h>
33 #include <isl/constraint.h>
35 #include "system.h"
36 #include "coretypes.h"
37 #include "backend.h"
38 #include "cfghooks.h"
39 #include "tree.h"
40 #include "gimple.h"
41 #include "fold-const.h"
42 #include "gimple-iterator.h"
43 #include "tree-ssa-loop.h"
44 #include "tree-pass.h"
45 #include "cfgloop.h"
46 #include "tree-data-ref.h"
47 #include "graphite-poly.h"
50 /* Add the constraints from the set S to the domain of MAP. */
52 static isl_map *
53 constrain_domain (isl_map *map, isl_set *s)
55 isl_space *d = isl_map_get_space (map);
56 isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
58 s = isl_set_set_tuple_id (s, id);
59 isl_space_free (d);
60 return isl_map_intersect_domain (map, s);
63 /* Constrain pdr->accesses with pdr->subscript_sizes and pbb->domain. */
65 static isl_map *
66 add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
68 isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
69 isl_set_copy (pdr->subscript_sizes));
70 x = constrain_domain (x, isl_set_copy (pbb->domain));
71 return x;
74 /* Returns all the memory reads in SCOP. */
76 static isl_union_map *
77 scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
79 int i, j;
80 poly_bb_p pbb;
81 poly_dr_p pdr;
82 isl_space *space = isl_set_get_space (scop->param_context);
83 isl_union_map *res = isl_union_map_empty (space);
85 FOR_EACH_VEC_ELT (pbbs, i, pbb)
87 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
88 if (pdr_read_p (pdr))
89 res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
92 return res;
95 /* Returns all the memory must writes in SCOP. */
97 static isl_union_map *
98 scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs)
100 int i, j;
101 poly_bb_p pbb;
102 poly_dr_p pdr;
103 isl_space *space = isl_set_get_space (scop->param_context);
104 isl_union_map *res = isl_union_map_empty (space);
106 FOR_EACH_VEC_ELT (pbbs, i, pbb)
108 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
109 if (pdr_write_p (pdr))
110 res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
113 return res;
116 /* Returns all the memory may writes in SCOP. */
118 static isl_union_map *
119 scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs)
121 int i, j;
122 poly_bb_p pbb;
123 poly_dr_p pdr;
124 isl_space *space = isl_set_get_space (scop->param_context);
125 isl_union_map *res = isl_union_map_empty (space);
127 FOR_EACH_VEC_ELT (pbbs, i, pbb)
129 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
130 if (pdr_may_write_p (pdr))
131 res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
134 return res;
137 /* Returns all the original schedules in SCOP. */
139 static isl_union_map *
140 scop_get_original_schedule (scop_p scop, vec<poly_bb_p> pbbs)
142 int i;
143 poly_bb_p pbb;
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 (pbbs, i, pbb)
149 res = isl_union_map_add_map
150 (res, constrain_domain (isl_map_copy (pbb->schedule),
151 isl_set_copy (pbb->domain)));
154 return res;
157 /* Helper function used on each MAP of a isl_union_map. Computes the
158 maximal output dimension. */
160 static isl_stat
161 max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
163 int global_max = *((int *) user);
164 isl_space *space = isl_map_get_space (map);
165 int nb_out = isl_space_dim (space, isl_dim_out);
167 if (global_max < nb_out)
168 *((int *) user) = nb_out;
170 isl_map_free (map);
171 isl_space_free (space);
172 return isl_stat_ok;
175 /* Extends the output dimension of MAP to MAX dimensions. */
177 static __isl_give isl_map *
178 extend_map (__isl_take isl_map *map, int max)
180 isl_space *space = isl_map_get_space (map);
181 int n = isl_space_dim (space, isl_dim_out);
183 isl_space_free (space);
184 return isl_map_add_dims (map, isl_dim_out, max - n);
187 /* Structure used to pass parameters to extend_schedule_1. */
189 struct extend_schedule_str {
190 int max;
191 isl_union_map *umap;
194 /* Helper function for extend_schedule. */
196 static isl_stat
197 extend_schedule_1 (__isl_take isl_map *map, void *user)
199 struct extend_schedule_str *str = (struct extend_schedule_str *) user;
200 str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
201 return isl_stat_ok;
204 /* Return a relation that has uniform output dimensions. */
206 static __isl_give isl_union_map *
207 extend_schedule (__isl_take isl_union_map *x)
209 int max = 0;
210 struct extend_schedule_str str;
212 isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
213 str.max = max;
214 str.umap = isl_union_map_empty (isl_union_map_get_space (x));
215 isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
216 isl_union_map_free (x);
217 return str.umap;
220 /* Applies SCHEDULE to the in and out dimensions of the dependences
221 DEPS and return the resulting relation. */
223 static isl_map *
224 apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
225 __isl_keep isl_union_map *deps)
227 isl_map *x;
228 isl_union_map *ux, *trans;
230 trans = isl_union_map_copy (schedule);
231 trans = extend_schedule (trans);
232 ux = isl_union_map_copy (deps);
233 ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
234 ux = isl_union_map_apply_range (ux, trans);
235 if (isl_union_map_is_empty (ux))
237 isl_union_map_free (ux);
238 return NULL;
240 x = isl_map_from_union_map (ux);
242 return x;
245 /* Return true when DEPS is non empty and the intersection of LEX with
246 the DEPS transformed by SCHEDULE is non empty. LEX is the relation
247 in which all the inputs before DEPTH occur at the same time as the
248 output, and the input at DEPTH occurs before output. */
250 bool
251 carries_deps (__isl_keep isl_union_map *schedule,
252 __isl_keep isl_union_map *deps,
253 int depth)
255 bool res;
256 int i;
257 isl_space *space;
258 isl_map *lex, *x;
259 isl_constraint *ineq;
261 if (isl_union_map_is_empty (deps))
262 return false;
264 x = apply_schedule_on_deps (schedule, deps);
265 if (x == NULL)
266 return false;
267 space = isl_map_get_space (x);
268 space = isl_space_range (space);
269 lex = isl_map_lex_le (space);
270 space = isl_map_get_space (x);
271 ineq = isl_inequality_alloc (isl_local_space_from_space (space));
273 for (i = 0; i < depth - 1; i++)
274 lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
276 /* in + 1 <= out */
277 ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
278 ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
279 ineq = isl_constraint_set_constant_si (ineq, -1);
280 lex = isl_map_add_constraint (lex, ineq);
281 x = isl_map_intersect (x, lex);
282 res = !isl_map_is_empty (x);
284 isl_map_free (x);
285 return res;
288 /* Compute the original data dependences in SCOP for all the reads and
289 writes in PBBS. */
291 static void
292 compute_deps (scop_p scop, vec<poly_bb_p> pbbs,
293 isl_union_map **must_raw,
294 isl_union_map **may_raw,
295 isl_union_map **must_raw_no_source,
296 isl_union_map **may_raw_no_source,
297 isl_union_map **must_war,
298 isl_union_map **may_war,
299 isl_union_map **must_war_no_source,
300 isl_union_map **may_war_no_source,
301 isl_union_map **must_waw,
302 isl_union_map **may_waw,
303 isl_union_map **must_waw_no_source,
304 isl_union_map **may_waw_no_source)
306 isl_union_map *reads = scop_get_reads (scop, pbbs);
307 isl_union_map *must_writes = scop_get_must_writes (scop, pbbs);
308 isl_union_map *may_writes = scop_get_may_writes (scop, pbbs);
309 isl_union_map *all_writes = isl_union_map_union
310 (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes));
311 isl_space *space = isl_union_map_get_space (all_writes);
312 isl_union_map *empty = isl_union_map_empty (space);
313 isl_union_map *original = scop_get_original_schedule (scop, pbbs);
315 isl_union_map_compute_flow (isl_union_map_copy (reads),
316 isl_union_map_copy (must_writes),
317 isl_union_map_copy (may_writes),
318 isl_union_map_copy (original),
319 must_raw, may_raw, must_raw_no_source,
320 may_raw_no_source);
321 isl_union_map_compute_flow (isl_union_map_copy (all_writes),
322 reads, empty,
323 isl_union_map_copy (original),
324 must_war, may_war, must_war_no_source,
325 may_war_no_source);
326 isl_union_map_compute_flow (all_writes, must_writes, may_writes,
327 original,
328 must_waw, may_waw, must_waw_no_source,
329 may_waw_no_source);
332 isl_union_map *
333 scop_get_dependences (scop_p scop)
335 isl_union_map *dependences;
337 if (!scop->must_raw)
338 compute_deps (scop, scop->pbbs,
339 &scop->must_raw, &scop->may_raw,
340 &scop->must_raw_no_source, &scop->may_raw_no_source,
341 &scop->must_war, &scop->may_war,
342 &scop->must_war_no_source, &scop->may_war_no_source,
343 &scop->must_waw, &scop->may_waw,
344 &scop->must_waw_no_source, &scop->may_waw_no_source);
346 dependences = isl_union_map_copy (scop->must_raw);
347 dependences = isl_union_map_union (dependences,
348 isl_union_map_copy (scop->must_war));
349 dependences = isl_union_map_union (dependences,
350 isl_union_map_copy (scop->must_waw));
351 dependences = isl_union_map_union (dependences,
352 isl_union_map_copy (scop->may_raw));
353 dependences = isl_union_map_union (dependences,
354 isl_union_map_copy (scop->may_war));
355 dependences = isl_union_map_union (dependences,
356 isl_union_map_copy (scop->may_waw));
358 if (dump_file)
360 fprintf (dump_file, "data dependences (\n");
361 print_isl_union_map (dump_file, dependences);
362 fprintf (dump_file, ")\n");
365 return dependences;
368 #endif /* HAVE_isl */