Update gcc-50 to SVN version 231263 (gcc-5-branch)
[dragonfly.git] / contrib / gcc-5.0 / gcc / graphite-dependences.c
blobafde45f063bc69506ef8a73d9d7709b4aed1a223
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 #include <isl/constraint.h>
26 #include <isl/set.h>
27 #include <isl/map.h>
28 #include <isl/union_map.h>
29 #include <isl/flow.h>
30 #include <isl/constraint.h>
31 #endif
33 #include "system.h"
34 #include "coretypes.h"
35 #include "hash-set.h"
36 #include "machmode.h"
37 #include "vec.h"
38 #include "double-int.h"
39 #include "input.h"
40 #include "alias.h"
41 #include "symtab.h"
42 #include "options.h"
43 #include "wide-int.h"
44 #include "inchash.h"
45 #include "tree.h"
46 #include "fold-const.h"
47 #include "predict.h"
48 #include "tm.h"
49 #include "hard-reg-set.h"
50 #include "input.h"
51 #include "function.h"
52 #include "dominance.h"
53 #include "cfg.h"
54 #include "basic-block.h"
55 #include "tree-ssa-alias.h"
56 #include "internal-fn.h"
57 #include "gimple-expr.h"
58 #include "is-a.h"
59 #include "gimple.h"
60 #include "gimple-iterator.h"
61 #include "tree-ssa-loop.h"
62 #include "tree-pass.h"
63 #include "cfgloop.h"
64 #include "tree-chrec.h"
65 #include "tree-data-ref.h"
66 #include "tree-scalar-evolution.h"
67 #include "sese.h"
69 #ifdef HAVE_isl
70 #include "graphite-poly.h"
72 isl_union_map *
73 scop_get_dependences (scop_p scop)
75 isl_union_map *dependences;
77 if (!scop->must_raw)
78 compute_deps (scop, SCOP_BBS (scop),
79 &scop->must_raw, &scop->may_raw,
80 &scop->must_raw_no_source, &scop->may_raw_no_source,
81 &scop->must_war, &scop->may_war,
82 &scop->must_war_no_source, &scop->may_war_no_source,
83 &scop->must_waw, &scop->may_waw,
84 &scop->must_waw_no_source, &scop->may_waw_no_source);
86 dependences = isl_union_map_copy (scop->must_raw);
87 dependences = isl_union_map_union (dependences,
88 isl_union_map_copy (scop->must_war));
89 dependences = isl_union_map_union (dependences,
90 isl_union_map_copy (scop->must_waw));
91 dependences = isl_union_map_union (dependences,
92 isl_union_map_copy (scop->may_raw));
93 dependences = isl_union_map_union (dependences,
94 isl_union_map_copy (scop->may_war));
95 dependences = isl_union_map_union (dependences,
96 isl_union_map_copy (scop->may_waw));
98 return dependences;
101 /* Add the constraints from the set S to the domain of MAP. */
103 static isl_map *
104 constrain_domain (isl_map *map, isl_set *s)
106 isl_space *d = isl_map_get_space (map);
107 isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
109 s = isl_set_set_tuple_id (s, id);
110 isl_space_free (d);
111 return isl_map_intersect_domain (map, s);
114 /* Constrain pdr->accesses with pdr->extent and pbb->domain. */
116 static isl_map *
117 add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
119 isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
120 isl_set_copy (pdr->extent));
121 x = constrain_domain (x, isl_set_copy (pbb->domain));
122 return x;
125 /* Returns all the memory reads in SCOP. */
127 static isl_union_map *
128 scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
130 int i, j;
131 poly_bb_p pbb;
132 poly_dr_p pdr;
133 isl_space *space = isl_set_get_space (scop->context);
134 isl_union_map *res = isl_union_map_empty (space);
136 FOR_EACH_VEC_ELT (pbbs, i, pbb)
138 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
139 if (pdr_read_p (pdr))
140 res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
143 return res;
146 /* Returns all the memory must writes in SCOP. */
148 static isl_union_map *
149 scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs)
151 int i, j;
152 poly_bb_p pbb;
153 poly_dr_p pdr;
154 isl_space *space = isl_set_get_space (scop->context);
155 isl_union_map *res = isl_union_map_empty (space);
157 FOR_EACH_VEC_ELT (pbbs, i, pbb)
159 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
160 if (pdr_write_p (pdr))
161 res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
164 return res;
167 /* Returns all the memory may writes in SCOP. */
169 static isl_union_map *
170 scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs)
172 int i, j;
173 poly_bb_p pbb;
174 poly_dr_p pdr;
175 isl_space *space = isl_set_get_space (scop->context);
176 isl_union_map *res = isl_union_map_empty (space);
178 FOR_EACH_VEC_ELT (pbbs, i, pbb)
180 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
181 if (pdr_may_write_p (pdr))
182 res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
185 return res;
188 /* Returns all the original schedules in SCOP. */
190 static isl_union_map *
191 scop_get_original_schedule (scop_p scop, vec<poly_bb_p> pbbs)
193 int i;
194 poly_bb_p pbb;
195 isl_space *space = isl_set_get_space (scop->context);
196 isl_union_map *res = isl_union_map_empty (space);
198 FOR_EACH_VEC_ELT (pbbs, i, pbb)
200 res = isl_union_map_add_map
201 (res, constrain_domain (isl_map_copy (pbb->schedule),
202 isl_set_copy (pbb->domain)));
205 return res;
208 /* Returns all the transformed schedules in SCOP. */
210 static isl_union_map *
211 scop_get_transformed_schedule (scop_p scop, vec<poly_bb_p> pbbs)
213 int i;
214 poly_bb_p pbb;
215 isl_space *space = isl_set_get_space (scop->context);
216 isl_union_map *res = isl_union_map_empty (space);
218 FOR_EACH_VEC_ELT (pbbs, i, pbb)
220 res = isl_union_map_add_map
221 (res, constrain_domain (isl_map_copy (pbb->transformed),
222 isl_set_copy (pbb->domain)));
225 return res;
228 /* Helper function used on each MAP of a isl_union_map. Computes the
229 maximal output dimension. */
231 static isl_stat
232 max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
234 int global_max = *((int *) user);
235 isl_space *space = isl_map_get_space (map);
236 int nb_out = isl_space_dim (space, isl_dim_out);
238 if (global_max < nb_out)
239 *((int *) user) = nb_out;
241 isl_map_free (map);
242 isl_space_free (space);
243 return isl_stat_ok;
246 /* Extends the output dimension of MAP to MAX dimensions. */
248 static __isl_give isl_map *
249 extend_map (__isl_take isl_map *map, int max)
251 isl_space *space = isl_map_get_space (map);
252 int n = isl_space_dim (space, isl_dim_out);
254 isl_space_free (space);
255 return isl_map_add_dims (map, isl_dim_out, max - n);
258 /* Structure used to pass parameters to extend_schedule_1. */
260 struct extend_schedule_str {
261 int max;
262 isl_union_map *umap;
265 /* Helper function for extend_schedule. */
267 static isl_stat
268 extend_schedule_1 (__isl_take isl_map *map, void *user)
270 struct extend_schedule_str *str = (struct extend_schedule_str *) user;
271 str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
272 return isl_stat_ok;
275 /* Return a relation that has uniform output dimensions. */
277 __isl_give isl_union_map *
278 extend_schedule (__isl_take isl_union_map *x)
280 int max = 0;
281 isl_stat res;
282 struct extend_schedule_str str;
284 res = isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
285 gcc_assert (res == isl_stat_ok);
287 str.max = max;
288 str.umap = isl_union_map_empty (isl_union_map_get_space (x));
289 res = isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
290 gcc_assert (res == isl_stat_ok);
292 isl_union_map_free (x);
293 return str.umap;
296 /* Applies SCHEDULE to the in and out dimensions of the dependences
297 DEPS and return the resulting relation. */
299 static isl_map *
300 apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
301 __isl_keep isl_union_map *deps)
303 isl_map *x;
304 isl_union_map *ux, *trans;
306 trans = isl_union_map_copy (schedule);
307 trans = extend_schedule (trans);
308 ux = isl_union_map_copy (deps);
309 ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
310 ux = isl_union_map_apply_range (ux, trans);
311 if (isl_union_map_is_empty (ux))
313 isl_union_map_free (ux);
314 return NULL;
316 x = isl_map_from_union_map (ux);
318 return x;
321 /* Return true when SCHEDULE does not violate the data DEPS: that is
322 when the intersection of LEX with the DEPS transformed by SCHEDULE
323 is empty. LEX is the relation in which the outputs occur before
324 the inputs. */
326 static bool
327 no_violations (__isl_keep isl_union_map *schedule,
328 __isl_keep isl_union_map *deps)
330 bool res;
331 isl_space *space;
332 isl_map *lex, *x;
334 if (isl_union_map_is_empty (deps))
335 return true;
337 x = apply_schedule_on_deps (schedule, deps);
338 space = isl_map_get_space (x);
339 space = isl_space_range (space);
340 lex = isl_map_lex_ge (space);
341 x = isl_map_intersect (x, lex);
342 res = isl_map_is_empty (x);
344 isl_map_free (x);
345 return res;
348 /* Return true when DEPS is non empty and the intersection of LEX with
349 the DEPS transformed by SCHEDULE is non empty. LEX is the relation
350 in which all the inputs before DEPTH occur at the same time as the
351 output, and the input at DEPTH occurs before output. */
353 bool
354 carries_deps (__isl_keep isl_union_map *schedule,
355 __isl_keep isl_union_map *deps,
356 int depth)
358 bool res;
359 int i;
360 isl_space *space;
361 isl_map *lex, *x;
362 isl_constraint *ineq;
364 if (isl_union_map_is_empty (deps))
365 return false;
367 x = apply_schedule_on_deps (schedule, deps);
368 if (x == NULL)
369 return false;
370 space = isl_map_get_space (x);
371 space = isl_space_range (space);
372 lex = isl_map_lex_le (space);
373 space = isl_map_get_space (x);
374 ineq = isl_inequality_alloc (isl_local_space_from_space (space));
376 for (i = 0; i < depth - 1; i++)
377 lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
379 /* in + 1 <= out */
380 ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
381 ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
382 ineq = isl_constraint_set_constant_si (ineq, -1);
383 lex = isl_map_add_constraint (lex, ineq);
384 x = isl_map_intersect (x, lex);
385 res = !isl_map_is_empty (x);
387 isl_map_free (x);
388 return res;
391 /* Subtract from the RAW, WAR, and WAW dependences those relations
392 that have been marked as belonging to an associative commutative
393 reduction. */
395 static void
396 subtract_commutative_associative_deps (scop_p scop,
397 vec<poly_bb_p> pbbs,
398 isl_union_map *original,
399 isl_union_map **must_raw,
400 isl_union_map **may_raw,
401 isl_union_map **must_raw_no_source,
402 isl_union_map **may_raw_no_source,
403 isl_union_map **must_war,
404 isl_union_map **may_war,
405 isl_union_map **must_war_no_source,
406 isl_union_map **may_war_no_source,
407 isl_union_map **must_waw,
408 isl_union_map **may_waw,
409 isl_union_map **must_waw_no_source,
410 isl_union_map **may_waw_no_source)
412 int i, j;
413 poly_bb_p pbb;
414 poly_dr_p pdr;
415 isl_space *space = isl_set_get_space (scop->context);
417 FOR_EACH_VEC_ELT (pbbs, i, pbb)
418 if (PBB_IS_REDUCTION (pbb))
420 int res;
421 isl_union_map *r = isl_union_map_empty (isl_space_copy (space));
422 isl_union_map *must_w = isl_union_map_empty (isl_space_copy (space));
423 isl_union_map *may_w = isl_union_map_empty (isl_space_copy (space));
424 isl_union_map *all_w;
425 isl_union_map *empty;
426 isl_union_map *x_must_raw;
427 isl_union_map *x_may_raw;
428 isl_union_map *x_must_raw_no_source;
429 isl_union_map *x_may_raw_no_source;
430 isl_union_map *x_must_war;
431 isl_union_map *x_may_war;
432 isl_union_map *x_must_war_no_source;
433 isl_union_map *x_may_war_no_source;
434 isl_union_map *x_must_waw;
435 isl_union_map *x_may_waw;
436 isl_union_map *x_must_waw_no_source;
437 isl_union_map *x_may_waw_no_source;
439 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
440 if (pdr_read_p (pdr))
441 r = isl_union_map_add_map (r, add_pdr_constraints (pdr, pbb));
443 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
444 if (pdr_write_p (pdr))
445 must_w = isl_union_map_add_map (must_w,
446 add_pdr_constraints (pdr, pbb));
448 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
449 if (pdr_may_write_p (pdr))
450 may_w = isl_union_map_add_map (may_w,
451 add_pdr_constraints (pdr, pbb));
453 all_w = isl_union_map_union
454 (isl_union_map_copy (must_w), isl_union_map_copy (may_w));
455 empty = isl_union_map_empty (isl_union_map_get_space (all_w));
457 res = isl_union_map_compute_flow (isl_union_map_copy (r),
458 isl_union_map_copy (must_w),
459 isl_union_map_copy (may_w),
460 isl_union_map_copy (original),
461 &x_must_raw, &x_may_raw,
462 &x_must_raw_no_source,
463 &x_may_raw_no_source);
464 gcc_assert (res == 0);
465 res = isl_union_map_compute_flow (isl_union_map_copy (all_w),
466 r, empty,
467 isl_union_map_copy (original),
468 &x_must_war, &x_may_war,
469 &x_must_war_no_source,
470 &x_may_war_no_source);
471 gcc_assert (res == 0);
472 res = isl_union_map_compute_flow (all_w, must_w, may_w,
473 isl_union_map_copy (original),
474 &x_must_waw, &x_may_waw,
475 &x_must_waw_no_source,
476 &x_may_waw_no_source);
477 gcc_assert (res == 0);
479 if (must_raw)
480 *must_raw = isl_union_map_subtract (*must_raw, x_must_raw);
481 else
482 isl_union_map_free (x_must_raw);
484 if (may_raw)
485 *may_raw = isl_union_map_subtract (*may_raw, x_may_raw);
486 else
487 isl_union_map_free (x_may_raw);
489 if (must_raw_no_source)
490 *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source,
491 x_must_raw_no_source);
492 else
493 isl_union_map_free (x_must_raw_no_source);
495 if (may_raw_no_source)
496 *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source,
497 x_may_raw_no_source);
498 else
499 isl_union_map_free (x_may_raw_no_source);
501 if (must_war)
502 *must_war = isl_union_map_subtract (*must_war, x_must_war);
503 else
504 isl_union_map_free (x_must_war);
506 if (may_war)
507 *may_war = isl_union_map_subtract (*may_war, x_may_war);
508 else
509 isl_union_map_free (x_may_war);
511 if (must_war_no_source)
512 *must_war_no_source = isl_union_map_subtract (*must_war_no_source,
513 x_must_war_no_source);
514 else
515 isl_union_map_free (x_must_war_no_source);
517 if (may_war_no_source)
518 *may_war_no_source = isl_union_map_subtract (*may_war_no_source,
519 x_may_war_no_source);
520 else
521 isl_union_map_free (x_may_war_no_source);
523 if (must_waw)
524 *must_waw = isl_union_map_subtract (*must_waw, x_must_waw);
525 else
526 isl_union_map_free (x_must_waw);
528 if (may_waw)
529 *may_waw = isl_union_map_subtract (*may_waw, x_may_waw);
530 else
531 isl_union_map_free (x_may_waw);
533 if (must_waw_no_source)
534 *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source,
535 x_must_waw_no_source);
536 else
537 isl_union_map_free (x_must_waw_no_source);
539 if (may_waw_no_source)
540 *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source,
541 x_may_waw_no_source);
542 else
543 isl_union_map_free (x_may_waw_no_source);
546 isl_union_map_free (original);
547 isl_space_free (space);
550 /* Compute the original data dependences in SCOP for all the reads and
551 writes in PBBS. */
553 void
554 compute_deps (scop_p scop, vec<poly_bb_p> pbbs,
555 isl_union_map **must_raw,
556 isl_union_map **may_raw,
557 isl_union_map **must_raw_no_source,
558 isl_union_map **may_raw_no_source,
559 isl_union_map **must_war,
560 isl_union_map **may_war,
561 isl_union_map **must_war_no_source,
562 isl_union_map **may_war_no_source,
563 isl_union_map **must_waw,
564 isl_union_map **may_waw,
565 isl_union_map **must_waw_no_source,
566 isl_union_map **may_waw_no_source)
568 isl_union_map *reads = scop_get_reads (scop, pbbs);
569 isl_union_map *must_writes = scop_get_must_writes (scop, pbbs);
570 isl_union_map *may_writes = scop_get_may_writes (scop, pbbs);
571 isl_union_map *all_writes = isl_union_map_union
572 (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes));
573 isl_space *space = isl_union_map_get_space (all_writes);
574 isl_union_map *empty = isl_union_map_empty (space);
575 isl_union_map *original = scop_get_original_schedule (scop, pbbs);
576 int res;
578 res = isl_union_map_compute_flow (isl_union_map_copy (reads),
579 isl_union_map_copy (must_writes),
580 isl_union_map_copy (may_writes),
581 isl_union_map_copy (original),
582 must_raw, may_raw, must_raw_no_source,
583 may_raw_no_source);
584 gcc_assert (res == 0);
585 res = isl_union_map_compute_flow (isl_union_map_copy (all_writes),
586 reads, empty,
587 isl_union_map_copy (original),
588 must_war, may_war, must_war_no_source,
589 may_war_no_source);
590 gcc_assert (res == 0);
591 res = isl_union_map_compute_flow (all_writes, must_writes, may_writes,
592 isl_union_map_copy (original),
593 must_waw, may_waw, must_waw_no_source,
594 may_waw_no_source);
595 gcc_assert (res == 0);
597 subtract_commutative_associative_deps
598 (scop, pbbs, original,
599 must_raw, may_raw, must_raw_no_source, may_raw_no_source,
600 must_war, may_war, must_war_no_source, may_war_no_source,
601 must_waw, may_waw, must_waw_no_source, may_waw_no_source);
604 /* Given a TRANSFORM, check whether it respects the original
605 dependences in SCOP. Returns true when TRANSFORM is a safe
606 transformation. */
608 static bool
609 transform_is_safe (scop_p scop, isl_union_map *transform)
611 bool res;
613 if (!scop->must_raw)
614 compute_deps (scop, SCOP_BBS (scop),
615 &scop->must_raw, &scop->may_raw,
616 &scop->must_raw_no_source, &scop->may_raw_no_source,
617 &scop->must_war, &scop->may_war,
618 &scop->must_war_no_source, &scop->may_war_no_source,
619 &scop->must_waw, &scop->may_waw,
620 &scop->must_waw_no_source, &scop->may_waw_no_source);
622 res = (no_violations (transform, scop->must_raw)
623 && no_violations (transform, scop->may_raw)
624 && no_violations (transform, scop->must_war)
625 && no_violations (transform, scop->may_war)
626 && no_violations (transform, scop->must_waw)
627 && no_violations (transform, scop->may_waw));
629 isl_union_map_free (transform);
630 return res;
633 /* Return true when the SCOP transformed schedule is correct. */
635 bool
636 graphite_legal_transform (scop_p scop)
638 int res;
639 isl_union_map *transform;
641 timevar_push (TV_GRAPHITE_DATA_DEPS);
642 transform = scop_get_transformed_schedule (scop, SCOP_BBS (scop));
643 res = transform_is_safe (scop, transform);
644 timevar_pop (TV_GRAPHITE_DATA_DEPS);
646 return res;
649 #endif