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