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)
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/>. */
27 #include <isl/union_map.h>
29 #include <isl/constraint.h>
30 #include <cloog/cloog.h>
31 #include <cloog/isl/domain.h>
35 #include "coretypes.h"
37 #include "basic-block.h"
38 #include "tree-ssa-alias.h"
39 #include "internal-fn.h"
40 #include "gimple-expr.h"
43 #include "gimple-iterator.h"
44 #include "tree-ssa-loop.h"
45 #include "tree-pass.h"
47 #include "tree-chrec.h"
48 #include "tree-data-ref.h"
49 #include "tree-scalar-evolution.h"
53 #include "graphite-poly.h"
54 #include "graphite-htab.h"
56 /* Add the constraints from the set S to the domain of MAP. */
59 constrain_domain (isl_map
*map
, isl_set
*s
)
61 isl_space
*d
= isl_map_get_space (map
);
62 isl_id
*id
= isl_space_get_tuple_id (d
, isl_dim_in
);
64 s
= isl_set_set_tuple_id (s
, id
);
66 return isl_map_intersect_domain (map
, s
);
69 /* Constrain pdr->accesses with pdr->extent and pbb->domain. */
72 add_pdr_constraints (poly_dr_p pdr
, poly_bb_p pbb
)
74 isl_map
*x
= isl_map_intersect_range (isl_map_copy (pdr
->accesses
),
75 isl_set_copy (pdr
->extent
));
76 x
= constrain_domain (x
, isl_set_copy (pbb
->domain
));
80 /* Returns all the memory reads in SCOP. */
82 static isl_union_map
*
83 scop_get_reads (scop_p scop
, vec
<poly_bb_p
> pbbs
)
88 isl_space
*space
= isl_set_get_space (scop
->context
);
89 isl_union_map
*res
= isl_union_map_empty (space
);
91 FOR_EACH_VEC_ELT (pbbs
, i
, pbb
)
93 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), j
, pdr
)
95 res
= isl_union_map_add_map (res
, add_pdr_constraints (pdr
, pbb
));
101 /* Returns all the memory must writes in SCOP. */
103 static isl_union_map
*
104 scop_get_must_writes (scop_p scop
, vec
<poly_bb_p
> pbbs
)
109 isl_space
*space
= isl_set_get_space (scop
->context
);
110 isl_union_map
*res
= isl_union_map_empty (space
);
112 FOR_EACH_VEC_ELT (pbbs
, i
, pbb
)
114 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), j
, pdr
)
115 if (pdr_write_p (pdr
))
116 res
= isl_union_map_add_map (res
, add_pdr_constraints (pdr
, pbb
));
122 /* Returns all the memory may writes in SCOP. */
124 static isl_union_map
*
125 scop_get_may_writes (scop_p scop
, vec
<poly_bb_p
> pbbs
)
130 isl_space
*space
= isl_set_get_space (scop
->context
);
131 isl_union_map
*res
= isl_union_map_empty (space
);
133 FOR_EACH_VEC_ELT (pbbs
, i
, pbb
)
135 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), j
, pdr
)
136 if (pdr_may_write_p (pdr
))
137 res
= isl_union_map_add_map (res
, add_pdr_constraints (pdr
, pbb
));
143 /* Returns all the original schedules in SCOP. */
145 static isl_union_map
*
146 scop_get_original_schedule (scop_p scop
, vec
<poly_bb_p
> pbbs
)
150 isl_space
*space
= isl_set_get_space (scop
->context
);
151 isl_union_map
*res
= isl_union_map_empty (space
);
153 FOR_EACH_VEC_ELT (pbbs
, i
, pbb
)
155 res
= isl_union_map_add_map
156 (res
, constrain_domain (isl_map_copy (pbb
->schedule
),
157 isl_set_copy (pbb
->domain
)));
163 /* Returns all the transformed schedules in SCOP. */
165 static isl_union_map
*
166 scop_get_transformed_schedule (scop_p scop
, vec
<poly_bb_p
> pbbs
)
170 isl_space
*space
= isl_set_get_space (scop
->context
);
171 isl_union_map
*res
= isl_union_map_empty (space
);
173 FOR_EACH_VEC_ELT (pbbs
, i
, pbb
)
175 res
= isl_union_map_add_map
176 (res
, constrain_domain (isl_map_copy (pbb
->transformed
),
177 isl_set_copy (pbb
->domain
)));
183 /* Helper function used on each MAP of a isl_union_map. Computes the
184 maximal output dimension. */
187 max_number_of_out_dimensions (__isl_take isl_map
*map
, void *user
)
189 int global_max
= *((int *) user
);
190 isl_space
*space
= isl_map_get_space (map
);
191 int nb_out
= isl_space_dim (space
, isl_dim_out
);
193 if (global_max
< nb_out
)
194 *((int *) user
) = nb_out
;
197 isl_space_free (space
);
201 /* Extends the output dimension of MAP to MAX dimensions. */
203 static __isl_give isl_map
*
204 extend_map (__isl_take isl_map
*map
, int max
)
206 isl_space
*space
= isl_map_get_space (map
);
207 int n
= isl_space_dim (space
, isl_dim_out
);
209 isl_space_free (space
);
210 return isl_map_add_dims (map
, isl_dim_out
, max
- n
);
213 /* Structure used to pass parameters to extend_schedule_1. */
215 struct extend_schedule_str
{
220 /* Helper function for extend_schedule. */
223 extend_schedule_1 (__isl_take isl_map
*map
, void *user
)
225 struct extend_schedule_str
*str
= (struct extend_schedule_str
*) user
;
226 str
->umap
= isl_union_map_add_map (str
->umap
, extend_map (map
, str
->max
));
230 /* Return a relation that has uniform output dimensions. */
232 __isl_give isl_union_map
*
233 extend_schedule (__isl_take isl_union_map
*x
)
237 struct extend_schedule_str str
;
239 res
= isl_union_map_foreach_map (x
, max_number_of_out_dimensions
, (void *) &max
);
240 gcc_assert (res
== 0);
243 str
.umap
= isl_union_map_empty (isl_union_map_get_space (x
));
244 res
= isl_union_map_foreach_map (x
, extend_schedule_1
, (void *) &str
);
245 gcc_assert (res
== 0);
247 isl_union_map_free (x
);
251 /* Applies SCHEDULE to the in and out dimensions of the dependences
252 DEPS and return the resulting relation. */
255 apply_schedule_on_deps (__isl_keep isl_union_map
*schedule
,
256 __isl_keep isl_union_map
*deps
)
259 isl_union_map
*ux
, *trans
;
261 trans
= isl_union_map_copy (schedule
);
262 trans
= extend_schedule (trans
);
263 ux
= isl_union_map_copy (deps
);
264 ux
= isl_union_map_apply_domain (ux
, isl_union_map_copy (trans
));
265 ux
= isl_union_map_apply_range (ux
, trans
);
266 x
= isl_map_from_union_map (ux
);
271 /* Return true when SCHEDULE does not violate the data DEPS: that is
272 when the intersection of LEX with the DEPS transformed by SCHEDULE
273 is empty. LEX is the relation in which the outputs occur before
277 no_violations (__isl_keep isl_union_map
*schedule
,
278 __isl_keep isl_union_map
*deps
)
284 if (isl_union_map_is_empty (deps
))
287 x
= apply_schedule_on_deps (schedule
, deps
);
288 space
= isl_map_get_space (x
);
289 space
= isl_space_range (space
);
290 lex
= isl_map_lex_ge (space
);
291 x
= isl_map_intersect (x
, lex
);
292 res
= isl_map_is_empty (x
);
298 /* Return true when DEPS is non empty and the intersection of LEX with
299 the DEPS transformed by SCHEDULE is non empty. LEX is the relation
300 in which all the inputs before DEPTH occur at the same time as the
301 output, and the input at DEPTH occurs before output. */
304 carries_deps (__isl_keep isl_union_map
*schedule
,
305 __isl_keep isl_union_map
*deps
,
312 isl_constraint
*ineq
;
314 if (isl_union_map_is_empty (deps
))
317 x
= apply_schedule_on_deps (schedule
, deps
);
318 space
= isl_map_get_space (x
);
319 space
= isl_space_range (space
);
320 lex
= isl_map_lex_le (space
);
321 space
= isl_map_get_space (x
);
322 ineq
= isl_inequality_alloc (isl_local_space_from_space (space
));
324 for (i
= 0; i
< depth
- 1; i
++)
325 lex
= isl_map_equate (lex
, isl_dim_in
, i
, isl_dim_out
, i
);
328 ineq
= isl_constraint_set_coefficient_si (ineq
, isl_dim_out
, depth
- 1, 1);
329 ineq
= isl_constraint_set_coefficient_si (ineq
, isl_dim_in
, depth
- 1, -1);
330 ineq
= isl_constraint_set_constant_si (ineq
, -1);
331 lex
= isl_map_add_constraint (lex
, ineq
);
332 x
= isl_map_intersect (x
, lex
);
333 res
= !isl_map_is_empty (x
);
339 /* Subtract from the RAW, WAR, and WAW dependences those relations
340 that have been marked as belonging to an associative commutative
344 subtract_commutative_associative_deps (scop_p scop
,
346 isl_union_map
*original
,
347 isl_union_map
**must_raw
,
348 isl_union_map
**may_raw
,
349 isl_union_map
**must_raw_no_source
,
350 isl_union_map
**may_raw_no_source
,
351 isl_union_map
**must_war
,
352 isl_union_map
**may_war
,
353 isl_union_map
**must_war_no_source
,
354 isl_union_map
**may_war_no_source
,
355 isl_union_map
**must_waw
,
356 isl_union_map
**may_waw
,
357 isl_union_map
**must_waw_no_source
,
358 isl_union_map
**may_waw_no_source
)
363 isl_space
*space
= isl_set_get_space (scop
->context
);
365 FOR_EACH_VEC_ELT (pbbs
, i
, pbb
)
366 if (PBB_IS_REDUCTION (pbb
))
369 isl_union_map
*r
= isl_union_map_empty (isl_space_copy (space
));
370 isl_union_map
*must_w
= isl_union_map_empty (isl_space_copy (space
));
371 isl_union_map
*may_w
= isl_union_map_empty (isl_space_copy (space
));
372 isl_union_map
*all_w
;
373 isl_union_map
*empty
;
374 isl_union_map
*x_must_raw
;
375 isl_union_map
*x_may_raw
;
376 isl_union_map
*x_must_raw_no_source
;
377 isl_union_map
*x_may_raw_no_source
;
378 isl_union_map
*x_must_war
;
379 isl_union_map
*x_may_war
;
380 isl_union_map
*x_must_war_no_source
;
381 isl_union_map
*x_may_war_no_source
;
382 isl_union_map
*x_must_waw
;
383 isl_union_map
*x_may_waw
;
384 isl_union_map
*x_must_waw_no_source
;
385 isl_union_map
*x_may_waw_no_source
;
387 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), j
, pdr
)
388 if (pdr_read_p (pdr
))
389 r
= isl_union_map_add_map (r
, add_pdr_constraints (pdr
, pbb
));
391 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), j
, pdr
)
392 if (pdr_write_p (pdr
))
393 must_w
= isl_union_map_add_map (must_w
,
394 add_pdr_constraints (pdr
, pbb
));
396 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), j
, pdr
)
397 if (pdr_may_write_p (pdr
))
398 may_w
= isl_union_map_add_map (may_w
,
399 add_pdr_constraints (pdr
, pbb
));
401 all_w
= isl_union_map_union
402 (isl_union_map_copy (must_w
), isl_union_map_copy (may_w
));
403 empty
= isl_union_map_empty (isl_union_map_get_space (all_w
));
405 res
= isl_union_map_compute_flow (isl_union_map_copy (r
),
406 isl_union_map_copy (must_w
),
407 isl_union_map_copy (may_w
),
408 isl_union_map_copy (original
),
409 &x_must_raw
, &x_may_raw
,
410 &x_must_raw_no_source
,
411 &x_may_raw_no_source
);
412 gcc_assert (res
== 0);
413 res
= isl_union_map_compute_flow (isl_union_map_copy (all_w
),
415 isl_union_map_copy (original
),
416 &x_must_war
, &x_may_war
,
417 &x_must_war_no_source
,
418 &x_may_war_no_source
);
419 gcc_assert (res
== 0);
420 res
= isl_union_map_compute_flow (all_w
, must_w
, may_w
,
421 isl_union_map_copy (original
),
422 &x_must_waw
, &x_may_waw
,
423 &x_must_waw_no_source
,
424 &x_may_waw_no_source
);
425 gcc_assert (res
== 0);
428 *must_raw
= isl_union_map_subtract (*must_raw
, x_must_raw
);
430 isl_union_map_free (x_must_raw
);
433 *may_raw
= isl_union_map_subtract (*may_raw
, x_may_raw
);
435 isl_union_map_free (x_may_raw
);
437 if (must_raw_no_source
)
438 *must_raw_no_source
= isl_union_map_subtract (*must_raw_no_source
,
439 x_must_raw_no_source
);
441 isl_union_map_free (x_must_raw_no_source
);
443 if (may_raw_no_source
)
444 *may_raw_no_source
= isl_union_map_subtract (*may_raw_no_source
,
445 x_may_raw_no_source
);
447 isl_union_map_free (x_may_raw_no_source
);
450 *must_war
= isl_union_map_subtract (*must_war
, x_must_war
);
452 isl_union_map_free (x_must_war
);
455 *may_war
= isl_union_map_subtract (*may_war
, x_may_war
);
457 isl_union_map_free (x_may_war
);
459 if (must_war_no_source
)
460 *must_war_no_source
= isl_union_map_subtract (*must_war_no_source
,
461 x_must_war_no_source
);
463 isl_union_map_free (x_must_war_no_source
);
465 if (may_war_no_source
)
466 *may_war_no_source
= isl_union_map_subtract (*may_war_no_source
,
467 x_may_war_no_source
);
469 isl_union_map_free (x_may_war_no_source
);
472 *must_waw
= isl_union_map_subtract (*must_waw
, x_must_waw
);
474 isl_union_map_free (x_must_waw
);
477 *may_waw
= isl_union_map_subtract (*may_waw
, x_may_waw
);
479 isl_union_map_free (x_may_waw
);
481 if (must_waw_no_source
)
482 *must_waw_no_source
= isl_union_map_subtract (*must_waw_no_source
,
483 x_must_waw_no_source
);
485 isl_union_map_free (x_must_waw_no_source
);
487 if (may_waw_no_source
)
488 *may_waw_no_source
= isl_union_map_subtract (*may_waw_no_source
,
489 x_may_waw_no_source
);
491 isl_union_map_free (x_may_waw_no_source
);
494 isl_union_map_free (original
);
495 isl_space_free (space
);
498 /* Compute the original data dependences in SCOP for all the reads and
502 compute_deps (scop_p scop
, vec
<poly_bb_p
> pbbs
,
503 isl_union_map
**must_raw
,
504 isl_union_map
**may_raw
,
505 isl_union_map
**must_raw_no_source
,
506 isl_union_map
**may_raw_no_source
,
507 isl_union_map
**must_war
,
508 isl_union_map
**may_war
,
509 isl_union_map
**must_war_no_source
,
510 isl_union_map
**may_war_no_source
,
511 isl_union_map
**must_waw
,
512 isl_union_map
**may_waw
,
513 isl_union_map
**must_waw_no_source
,
514 isl_union_map
**may_waw_no_source
)
516 isl_union_map
*reads
= scop_get_reads (scop
, pbbs
);
517 isl_union_map
*must_writes
= scop_get_must_writes (scop
, pbbs
);
518 isl_union_map
*may_writes
= scop_get_may_writes (scop
, pbbs
);
519 isl_union_map
*all_writes
= isl_union_map_union
520 (isl_union_map_copy (must_writes
), isl_union_map_copy (may_writes
));
521 isl_space
*space
= isl_union_map_get_space (all_writes
);
522 isl_union_map
*empty
= isl_union_map_empty (space
);
523 isl_union_map
*original
= scop_get_original_schedule (scop
, pbbs
);
526 res
= isl_union_map_compute_flow (isl_union_map_copy (reads
),
527 isl_union_map_copy (must_writes
),
528 isl_union_map_copy (may_writes
),
529 isl_union_map_copy (original
),
530 must_raw
, may_raw
, must_raw_no_source
,
532 gcc_assert (res
== 0);
533 res
= isl_union_map_compute_flow (isl_union_map_copy (all_writes
),
535 isl_union_map_copy (original
),
536 must_war
, may_war
, must_war_no_source
,
538 gcc_assert (res
== 0);
539 res
= isl_union_map_compute_flow (all_writes
, must_writes
, may_writes
,
540 isl_union_map_copy (original
),
541 must_waw
, may_waw
, must_waw_no_source
,
543 gcc_assert (res
== 0);
545 subtract_commutative_associative_deps
546 (scop
, pbbs
, original
,
547 must_raw
, may_raw
, must_raw_no_source
, may_raw_no_source
,
548 must_war
, may_war
, must_war_no_source
, may_war_no_source
,
549 must_waw
, may_waw
, must_waw_no_source
, may_waw_no_source
);
552 /* Given a TRANSFORM, check whether it respects the original
553 dependences in SCOP. Returns true when TRANSFORM is a safe
557 transform_is_safe (scop_p scop
, isl_union_map
*transform
)
562 compute_deps (scop
, SCOP_BBS (scop
),
563 &scop
->must_raw
, &scop
->may_raw
,
564 &scop
->must_raw_no_source
, &scop
->may_raw_no_source
,
565 &scop
->must_war
, &scop
->may_war
,
566 &scop
->must_war_no_source
, &scop
->may_war_no_source
,
567 &scop
->must_waw
, &scop
->may_waw
,
568 &scop
->must_waw_no_source
, &scop
->may_waw_no_source
);
570 res
= (no_violations (transform
, scop
->must_raw
)
571 && no_violations (transform
, scop
->may_raw
)
572 && no_violations (transform
, scop
->must_war
)
573 && no_violations (transform
, scop
->may_war
)
574 && no_violations (transform
, scop
->must_waw
)
575 && no_violations (transform
, scop
->may_waw
));
577 isl_union_map_free (transform
);
581 /* Return true when the SCOP transformed schedule is correct. */
584 graphite_legal_transform (scop_p scop
)
587 isl_union_map
*transform
;
589 timevar_push (TV_GRAPHITE_DATA_DEPS
);
590 transform
= scop_get_transformed_schedule (scop
, SCOP_BBS (scop
));
591 res
= transform_is_safe (scop
, transform
);
592 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
597 /* Return true when the loop at DEPTH carries dependences. BODY is
598 the body of the loop. */
601 loop_level_carries_dependences (scop_p scop
, vec
<poly_bb_p
> body
,
604 isl_union_map
*transform
= scop_get_transformed_schedule (scop
, body
);
605 isl_union_map
*must_raw
, *may_raw
;
606 isl_union_map
*must_war
, *may_war
;
607 isl_union_map
*must_waw
, *may_waw
;
610 compute_deps (scop
, body
,
611 &must_raw
, &may_raw
, NULL
, NULL
,
612 &must_war
, &may_war
, NULL
, NULL
,
613 &must_waw
, &may_waw
, NULL
, NULL
);
615 res
= (carries_deps (transform
, must_raw
, depth
)
616 || carries_deps (transform
, may_raw
, depth
)
617 || carries_deps (transform
, must_war
, depth
)
618 || carries_deps (transform
, may_war
, depth
)
619 || carries_deps (transform
, must_waw
, depth
)
620 || carries_deps (transform
, may_waw
, depth
));
622 isl_union_map_free (transform
);
623 isl_union_map_free (must_raw
);
624 isl_union_map_free (may_raw
);
625 isl_union_map_free (must_war
);
626 isl_union_map_free (may_war
);
627 isl_union_map_free (must_waw
);
628 isl_union_map_free (may_waw
);
632 /* Returns true when the loop L at level DEPTH is parallel.
633 BB_PBB_MAPPING is a map between a basic_block and its related
637 loop_is_parallel_p (loop_p loop
, bb_pbb_htab_type
*bb_pbb_mapping
, int depth
)
642 timevar_push (TV_GRAPHITE_DATA_DEPS
);
643 auto_vec
<poly_bb_p
, 3> body
;
644 scop
= get_loop_body_pbbs (loop
, bb_pbb_mapping
, &body
);
645 dependences
= loop_level_carries_dependences (scop
, body
, depth
);
646 timevar_pop (TV_GRAPHITE_DATA_DEPS
);