2014-12-12 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / graphite-dependences.c
blobb79c69216121ac96ae658309d6e431711515a184
1 /* Data dependence analysis for Graphite.
2 Copyright (C) 2009-2014 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 #include <isl/set.h>
26 #include <isl/map.h>
27 #include <isl/union_map.h>
28 #include <isl/flow.h>
29 #include <isl/constraint.h>
30 #endif
32 #include "system.h"
33 #include "coretypes.h"
34 #include "tree.h"
35 #include "predict.h"
36 #include "vec.h"
37 #include "hashtab.h"
38 #include "hash-set.h"
39 #include "machmode.h"
40 #include "tm.h"
41 #include "hard-reg-set.h"
42 #include "input.h"
43 #include "function.h"
44 #include "dominance.h"
45 #include "cfg.h"
46 #include "basic-block.h"
47 #include "tree-ssa-alias.h"
48 #include "internal-fn.h"
49 #include "gimple-expr.h"
50 #include "is-a.h"
51 #include "gimple.h"
52 #include "gimple-iterator.h"
53 #include "tree-ssa-loop.h"
54 #include "tree-pass.h"
55 #include "cfgloop.h"
56 #include "tree-chrec.h"
57 #include "tree-data-ref.h"
58 #include "tree-scalar-evolution.h"
59 #include "sese.h"
61 #ifdef HAVE_isl
62 #include "graphite-poly.h"
64 isl_union_map *
65 scop_get_dependences (scop_p scop)
67 isl_union_map *dependences;
69 if (!scop->must_raw)
70 compute_deps (scop, SCOP_BBS (scop),
71 &scop->must_raw, &scop->may_raw,
72 &scop->must_raw_no_source, &scop->may_raw_no_source,
73 &scop->must_war, &scop->may_war,
74 &scop->must_war_no_source, &scop->may_war_no_source,
75 &scop->must_waw, &scop->may_waw,
76 &scop->must_waw_no_source, &scop->may_waw_no_source);
78 dependences = isl_union_map_copy (scop->must_raw);
79 dependences = isl_union_map_union (dependences,
80 isl_union_map_copy (scop->must_war));
81 dependences = isl_union_map_union (dependences,
82 isl_union_map_copy (scop->must_waw));
83 dependences = isl_union_map_union (dependences,
84 isl_union_map_copy (scop->may_raw));
85 dependences = isl_union_map_union (dependences,
86 isl_union_map_copy (scop->may_war));
87 dependences = isl_union_map_union (dependences,
88 isl_union_map_copy (scop->may_waw));
90 return dependences;
93 /* Add the constraints from the set S to the domain of MAP. */
95 static isl_map *
96 constrain_domain (isl_map *map, isl_set *s)
98 isl_space *d = isl_map_get_space (map);
99 isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
101 s = isl_set_set_tuple_id (s, id);
102 isl_space_free (d);
103 return isl_map_intersect_domain (map, s);
106 /* Constrain pdr->accesses with pdr->extent and pbb->domain. */
108 static isl_map *
109 add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
111 isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
112 isl_set_copy (pdr->extent));
113 x = constrain_domain (x, isl_set_copy (pbb->domain));
114 return x;
117 /* Returns all the memory reads in SCOP. */
119 static isl_union_map *
120 scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
122 int i, j;
123 poly_bb_p pbb;
124 poly_dr_p pdr;
125 isl_space *space = isl_set_get_space (scop->context);
126 isl_union_map *res = isl_union_map_empty (space);
128 FOR_EACH_VEC_ELT (pbbs, i, pbb)
130 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
131 if (pdr_read_p (pdr))
132 res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
135 return res;
138 /* Returns all the memory must writes in SCOP. */
140 static isl_union_map *
141 scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs)
143 int i, j;
144 poly_bb_p pbb;
145 poly_dr_p pdr;
146 isl_space *space = isl_set_get_space (scop->context);
147 isl_union_map *res = isl_union_map_empty (space);
149 FOR_EACH_VEC_ELT (pbbs, i, pbb)
151 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
152 if (pdr_write_p (pdr))
153 res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
156 return res;
159 /* Returns all the memory may writes in SCOP. */
161 static isl_union_map *
162 scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs)
164 int i, j;
165 poly_bb_p pbb;
166 poly_dr_p pdr;
167 isl_space *space = isl_set_get_space (scop->context);
168 isl_union_map *res = isl_union_map_empty (space);
170 FOR_EACH_VEC_ELT (pbbs, i, pbb)
172 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
173 if (pdr_may_write_p (pdr))
174 res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
177 return res;
180 /* Returns all the original schedules in SCOP. */
182 static isl_union_map *
183 scop_get_original_schedule (scop_p scop, vec<poly_bb_p> pbbs)
185 int i;
186 poly_bb_p pbb;
187 isl_space *space = isl_set_get_space (scop->context);
188 isl_union_map *res = isl_union_map_empty (space);
190 FOR_EACH_VEC_ELT (pbbs, i, pbb)
192 res = isl_union_map_add_map
193 (res, constrain_domain (isl_map_copy (pbb->schedule),
194 isl_set_copy (pbb->domain)));
197 return res;
200 /* Returns all the transformed schedules in SCOP. */
202 static isl_union_map *
203 scop_get_transformed_schedule (scop_p scop, vec<poly_bb_p> pbbs)
205 int i;
206 poly_bb_p pbb;
207 isl_space *space = isl_set_get_space (scop->context);
208 isl_union_map *res = isl_union_map_empty (space);
210 FOR_EACH_VEC_ELT (pbbs, i, pbb)
212 res = isl_union_map_add_map
213 (res, constrain_domain (isl_map_copy (pbb->transformed),
214 isl_set_copy (pbb->domain)));
217 return res;
220 /* Helper function used on each MAP of a isl_union_map. Computes the
221 maximal output dimension. */
223 static int
224 max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
226 int global_max = *((int *) user);
227 isl_space *space = isl_map_get_space (map);
228 int nb_out = isl_space_dim (space, isl_dim_out);
230 if (global_max < nb_out)
231 *((int *) user) = nb_out;
233 isl_map_free (map);
234 isl_space_free (space);
235 return 0;
238 /* Extends the output dimension of MAP to MAX dimensions. */
240 static __isl_give isl_map *
241 extend_map (__isl_take isl_map *map, int max)
243 isl_space *space = isl_map_get_space (map);
244 int n = isl_space_dim (space, isl_dim_out);
246 isl_space_free (space);
247 return isl_map_add_dims (map, isl_dim_out, max - n);
250 /* Structure used to pass parameters to extend_schedule_1. */
252 struct extend_schedule_str {
253 int max;
254 isl_union_map *umap;
257 /* Helper function for extend_schedule. */
259 static int
260 extend_schedule_1 (__isl_take isl_map *map, void *user)
262 struct extend_schedule_str *str = (struct extend_schedule_str *) user;
263 str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
264 return 0;
267 /* Return a relation that has uniform output dimensions. */
269 __isl_give isl_union_map *
270 extend_schedule (__isl_take isl_union_map *x)
272 int max = 0;
273 int res;
274 struct extend_schedule_str str;
276 res = isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
277 gcc_assert (res == 0);
279 str.max = max;
280 str.umap = isl_union_map_empty (isl_union_map_get_space (x));
281 res = isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
282 gcc_assert (res == 0);
284 isl_union_map_free (x);
285 return str.umap;
288 /* Applies SCHEDULE to the in and out dimensions of the dependences
289 DEPS and return the resulting relation. */
291 static isl_map *
292 apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
293 __isl_keep isl_union_map *deps)
295 isl_map *x;
296 isl_union_map *ux, *trans;
298 trans = isl_union_map_copy (schedule);
299 trans = extend_schedule (trans);
300 ux = isl_union_map_copy (deps);
301 ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
302 ux = isl_union_map_apply_range (ux, trans);
303 if (isl_union_map_is_empty (ux))
305 isl_union_map_free (ux);
306 return NULL;
308 x = isl_map_from_union_map (ux);
310 return x;
313 /* Return true when SCHEDULE does not violate the data DEPS: that is
314 when the intersection of LEX with the DEPS transformed by SCHEDULE
315 is empty. LEX is the relation in which the outputs occur before
316 the inputs. */
318 static bool
319 no_violations (__isl_keep isl_union_map *schedule,
320 __isl_keep isl_union_map *deps)
322 bool res;
323 isl_space *space;
324 isl_map *lex, *x;
326 if (isl_union_map_is_empty (deps))
327 return true;
329 x = apply_schedule_on_deps (schedule, deps);
330 space = isl_map_get_space (x);
331 space = isl_space_range (space);
332 lex = isl_map_lex_ge (space);
333 x = isl_map_intersect (x, lex);
334 res = isl_map_is_empty (x);
336 isl_map_free (x);
337 return res;
340 /* Return true when DEPS is non empty and the intersection of LEX with
341 the DEPS transformed by SCHEDULE is non empty. LEX is the relation
342 in which all the inputs before DEPTH occur at the same time as the
343 output, and the input at DEPTH occurs before output. */
345 bool
346 carries_deps (__isl_keep isl_union_map *schedule,
347 __isl_keep isl_union_map *deps,
348 int depth)
350 bool res;
351 int i;
352 isl_space *space;
353 isl_map *lex, *x;
354 isl_constraint *ineq;
356 if (isl_union_map_is_empty (deps))
357 return false;
359 x = apply_schedule_on_deps (schedule, deps);
360 if (x == NULL)
361 return false;
362 space = isl_map_get_space (x);
363 space = isl_space_range (space);
364 lex = isl_map_lex_le (space);
365 space = isl_map_get_space (x);
366 ineq = isl_inequality_alloc (isl_local_space_from_space (space));
368 for (i = 0; i < depth - 1; i++)
369 lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
371 /* in + 1 <= out */
372 ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
373 ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
374 ineq = isl_constraint_set_constant_si (ineq, -1);
375 lex = isl_map_add_constraint (lex, ineq);
376 x = isl_map_intersect (x, lex);
377 res = !isl_map_is_empty (x);
379 isl_map_free (x);
380 return res;
383 /* Subtract from the RAW, WAR, and WAW dependences those relations
384 that have been marked as belonging to an associative commutative
385 reduction. */
387 static void
388 subtract_commutative_associative_deps (scop_p scop,
389 vec<poly_bb_p> pbbs,
390 isl_union_map *original,
391 isl_union_map **must_raw,
392 isl_union_map **may_raw,
393 isl_union_map **must_raw_no_source,
394 isl_union_map **may_raw_no_source,
395 isl_union_map **must_war,
396 isl_union_map **may_war,
397 isl_union_map **must_war_no_source,
398 isl_union_map **may_war_no_source,
399 isl_union_map **must_waw,
400 isl_union_map **may_waw,
401 isl_union_map **must_waw_no_source,
402 isl_union_map **may_waw_no_source)
404 int i, j;
405 poly_bb_p pbb;
406 poly_dr_p pdr;
407 isl_space *space = isl_set_get_space (scop->context);
409 FOR_EACH_VEC_ELT (pbbs, i, pbb)
410 if (PBB_IS_REDUCTION (pbb))
412 int res;
413 isl_union_map *r = isl_union_map_empty (isl_space_copy (space));
414 isl_union_map *must_w = isl_union_map_empty (isl_space_copy (space));
415 isl_union_map *may_w = isl_union_map_empty (isl_space_copy (space));
416 isl_union_map *all_w;
417 isl_union_map *empty;
418 isl_union_map *x_must_raw;
419 isl_union_map *x_may_raw;
420 isl_union_map *x_must_raw_no_source;
421 isl_union_map *x_may_raw_no_source;
422 isl_union_map *x_must_war;
423 isl_union_map *x_may_war;
424 isl_union_map *x_must_war_no_source;
425 isl_union_map *x_may_war_no_source;
426 isl_union_map *x_must_waw;
427 isl_union_map *x_may_waw;
428 isl_union_map *x_must_waw_no_source;
429 isl_union_map *x_may_waw_no_source;
431 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
432 if (pdr_read_p (pdr))
433 r = isl_union_map_add_map (r, add_pdr_constraints (pdr, pbb));
435 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
436 if (pdr_write_p (pdr))
437 must_w = isl_union_map_add_map (must_w,
438 add_pdr_constraints (pdr, pbb));
440 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
441 if (pdr_may_write_p (pdr))
442 may_w = isl_union_map_add_map (may_w,
443 add_pdr_constraints (pdr, pbb));
445 all_w = isl_union_map_union
446 (isl_union_map_copy (must_w), isl_union_map_copy (may_w));
447 empty = isl_union_map_empty (isl_union_map_get_space (all_w));
449 res = isl_union_map_compute_flow (isl_union_map_copy (r),
450 isl_union_map_copy (must_w),
451 isl_union_map_copy (may_w),
452 isl_union_map_copy (original),
453 &x_must_raw, &x_may_raw,
454 &x_must_raw_no_source,
455 &x_may_raw_no_source);
456 gcc_assert (res == 0);
457 res = isl_union_map_compute_flow (isl_union_map_copy (all_w),
458 r, empty,
459 isl_union_map_copy (original),
460 &x_must_war, &x_may_war,
461 &x_must_war_no_source,
462 &x_may_war_no_source);
463 gcc_assert (res == 0);
464 res = isl_union_map_compute_flow (all_w, must_w, may_w,
465 isl_union_map_copy (original),
466 &x_must_waw, &x_may_waw,
467 &x_must_waw_no_source,
468 &x_may_waw_no_source);
469 gcc_assert (res == 0);
471 if (must_raw)
472 *must_raw = isl_union_map_subtract (*must_raw, x_must_raw);
473 else
474 isl_union_map_free (x_must_raw);
476 if (may_raw)
477 *may_raw = isl_union_map_subtract (*may_raw, x_may_raw);
478 else
479 isl_union_map_free (x_may_raw);
481 if (must_raw_no_source)
482 *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source,
483 x_must_raw_no_source);
484 else
485 isl_union_map_free (x_must_raw_no_source);
487 if (may_raw_no_source)
488 *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source,
489 x_may_raw_no_source);
490 else
491 isl_union_map_free (x_may_raw_no_source);
493 if (must_war)
494 *must_war = isl_union_map_subtract (*must_war, x_must_war);
495 else
496 isl_union_map_free (x_must_war);
498 if (may_war)
499 *may_war = isl_union_map_subtract (*may_war, x_may_war);
500 else
501 isl_union_map_free (x_may_war);
503 if (must_war_no_source)
504 *must_war_no_source = isl_union_map_subtract (*must_war_no_source,
505 x_must_war_no_source);
506 else
507 isl_union_map_free (x_must_war_no_source);
509 if (may_war_no_source)
510 *may_war_no_source = isl_union_map_subtract (*may_war_no_source,
511 x_may_war_no_source);
512 else
513 isl_union_map_free (x_may_war_no_source);
515 if (must_waw)
516 *must_waw = isl_union_map_subtract (*must_waw, x_must_waw);
517 else
518 isl_union_map_free (x_must_waw);
520 if (may_waw)
521 *may_waw = isl_union_map_subtract (*may_waw, x_may_waw);
522 else
523 isl_union_map_free (x_may_waw);
525 if (must_waw_no_source)
526 *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source,
527 x_must_waw_no_source);
528 else
529 isl_union_map_free (x_must_waw_no_source);
531 if (may_waw_no_source)
532 *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source,
533 x_may_waw_no_source);
534 else
535 isl_union_map_free (x_may_waw_no_source);
538 isl_union_map_free (original);
539 isl_space_free (space);
542 /* Compute the original data dependences in SCOP for all the reads and
543 writes in PBBS. */
545 void
546 compute_deps (scop_p scop, vec<poly_bb_p> pbbs,
547 isl_union_map **must_raw,
548 isl_union_map **may_raw,
549 isl_union_map **must_raw_no_source,
550 isl_union_map **may_raw_no_source,
551 isl_union_map **must_war,
552 isl_union_map **may_war,
553 isl_union_map **must_war_no_source,
554 isl_union_map **may_war_no_source,
555 isl_union_map **must_waw,
556 isl_union_map **may_waw,
557 isl_union_map **must_waw_no_source,
558 isl_union_map **may_waw_no_source)
560 isl_union_map *reads = scop_get_reads (scop, pbbs);
561 isl_union_map *must_writes = scop_get_must_writes (scop, pbbs);
562 isl_union_map *may_writes = scop_get_may_writes (scop, pbbs);
563 isl_union_map *all_writes = isl_union_map_union
564 (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes));
565 isl_space *space = isl_union_map_get_space (all_writes);
566 isl_union_map *empty = isl_union_map_empty (space);
567 isl_union_map *original = scop_get_original_schedule (scop, pbbs);
568 int res;
570 res = isl_union_map_compute_flow (isl_union_map_copy (reads),
571 isl_union_map_copy (must_writes),
572 isl_union_map_copy (may_writes),
573 isl_union_map_copy (original),
574 must_raw, may_raw, must_raw_no_source,
575 may_raw_no_source);
576 gcc_assert (res == 0);
577 res = isl_union_map_compute_flow (isl_union_map_copy (all_writes),
578 reads, empty,
579 isl_union_map_copy (original),
580 must_war, may_war, must_war_no_source,
581 may_war_no_source);
582 gcc_assert (res == 0);
583 res = isl_union_map_compute_flow (all_writes, must_writes, may_writes,
584 isl_union_map_copy (original),
585 must_waw, may_waw, must_waw_no_source,
586 may_waw_no_source);
587 gcc_assert (res == 0);
589 subtract_commutative_associative_deps
590 (scop, pbbs, original,
591 must_raw, may_raw, must_raw_no_source, may_raw_no_source,
592 must_war, may_war, must_war_no_source, may_war_no_source,
593 must_waw, may_waw, must_waw_no_source, may_waw_no_source);
596 /* Given a TRANSFORM, check whether it respects the original
597 dependences in SCOP. Returns true when TRANSFORM is a safe
598 transformation. */
600 static bool
601 transform_is_safe (scop_p scop, isl_union_map *transform)
603 bool res;
605 if (!scop->must_raw)
606 compute_deps (scop, SCOP_BBS (scop),
607 &scop->must_raw, &scop->may_raw,
608 &scop->must_raw_no_source, &scop->may_raw_no_source,
609 &scop->must_war, &scop->may_war,
610 &scop->must_war_no_source, &scop->may_war_no_source,
611 &scop->must_waw, &scop->may_waw,
612 &scop->must_waw_no_source, &scop->may_waw_no_source);
614 res = (no_violations (transform, scop->must_raw)
615 && no_violations (transform, scop->may_raw)
616 && no_violations (transform, scop->must_war)
617 && no_violations (transform, scop->may_war)
618 && no_violations (transform, scop->must_waw)
619 && no_violations (transform, scop->may_waw));
621 isl_union_map_free (transform);
622 return res;
625 /* Return true when the SCOP transformed schedule is correct. */
627 bool
628 graphite_legal_transform (scop_p scop)
630 int res;
631 isl_union_map *transform;
633 timevar_push (TV_GRAPHITE_DATA_DEPS);
634 transform = scop_get_transformed_schedule (scop, SCOP_BBS (scop));
635 res = transform_is_safe (scop, transform);
636 timevar_pop (TV_GRAPHITE_DATA_DEPS);
638 return res;
641 #endif