1 /* Data dependence analysis for Graphite.
2 Copyright (C) 2009, 2010 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/>. */
24 #include "coretypes.h"
25 #include "tree-flow.h"
26 #include "tree-dump.h"
28 #include "tree-chrec.h"
29 #include "tree-data-ref.h"
30 #include "tree-scalar-evolution.h"
35 #include "graphite-ppl.h"
36 #include "graphite-poly.h"
37 #include "graphite-dependences.h"
39 /* Returns a new polyhedral Data Dependence Relation (DDR). SOURCE is
40 the source data reference, SINK is the sink data reference. When
41 the Data Dependence Polyhedron DDP is not NULL or not empty, SOURCE
42 and SINK are in dependence as described by DDP. */
45 new_poly_ddr (poly_dr_p source
, poly_dr_p sink
,
46 ppl_Pointset_Powerset_C_Polyhedron_t ddp
,
47 bool original_scattering_p
)
49 poly_ddr_p pddr
= XNEW (struct poly_ddr
);
51 PDDR_SOURCE (pddr
) = source
;
52 PDDR_SINK (pddr
) = sink
;
53 PDDR_DDP (pddr
) = ddp
;
54 PDDR_ORIGINAL_SCATTERING_P (pddr
) = original_scattering_p
;
57 || ppl_powerset_is_empty (ddp
,
58 scop_nb_params (PBB_SCOP (PDR_PBB (source
)))))
59 PDDR_KIND (pddr
) = no_dependence
;
61 PDDR_KIND (pddr
) = has_dependence
;
66 /* Free the poly_ddr_p P. */
69 free_poly_ddr (void *p
)
71 poly_ddr_p pddr
= (poly_ddr_p
) p
;
72 ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr
));
76 /* Comparison function for poly_ddr hash table. */
79 eq_poly_ddr_p (const void *pddr1
, const void *pddr2
)
81 const struct poly_ddr
*p1
= (const struct poly_ddr
*) pddr1
;
82 const struct poly_ddr
*p2
= (const struct poly_ddr
*) pddr2
;
84 return (PDDR_SOURCE (p1
) == PDDR_SOURCE (p2
)
85 && PDDR_SINK (p1
) == PDDR_SINK (p2
));
88 /* Hash function for poly_ddr hashtable. */
91 hash_poly_ddr_p (const void *pddr
)
93 const struct poly_ddr
*p
= (const struct poly_ddr
*) pddr
;
95 return (hashval_t
) ((long) PDDR_SOURCE (p
) + (long) PDDR_SINK (p
));
98 /* Returns true when PDDR has no dependence. */
101 pddr_is_empty (poly_ddr_p pddr
)
106 gcc_assert (PDDR_KIND (pddr
) != unknown_dependence
);
108 return PDDR_KIND (pddr
) == no_dependence
? true : false;
111 /* Prints to FILE the layout of the dependence polyhedron of PDDR:
116 | T1 and T2 the scattering dimensions for PDDR_SOURCE and PDDR_SINK
117 | I1 and I2 the iteration domains
118 | S1 and S2 the subscripts
119 | G the global parameters. */
122 print_dependence_polyhedron_layout (FILE *file
, poly_ddr_p pddr
)
124 poly_dr_p pdr1
= PDDR_SOURCE (pddr
);
125 poly_dr_p pdr2
= PDDR_SINK (pddr
);
126 poly_bb_p pbb1
= PDR_PBB (pdr1
);
127 poly_bb_p pbb2
= PDR_PBB (pdr2
);
130 graphite_dim_t tdim1
= PDDR_ORIGINAL_SCATTERING_P (pddr
) ?
131 pbb_nb_scattering_orig (pbb1
) : pbb_nb_scattering_transform (pbb1
);
132 graphite_dim_t tdim2
= PDDR_ORIGINAL_SCATTERING_P (pddr
) ?
133 pbb_nb_scattering_orig (pbb2
) : pbb_nb_scattering_transform (pbb2
);
134 graphite_dim_t idim1
= pbb_dim_iter_domain (pbb1
);
135 graphite_dim_t idim2
= pbb_dim_iter_domain (pbb2
);
136 graphite_dim_t sdim1
= PDR_NB_SUBSCRIPTS (pdr1
) + 1;
137 graphite_dim_t sdim2
= PDR_NB_SUBSCRIPTS (pdr2
) + 1;
138 graphite_dim_t gdim
= scop_nb_params (PBB_SCOP (pbb1
));
140 fprintf (file
, "# eq");
142 for (i
= 0; i
< tdim1
; i
++)
143 fprintf (file
, " t1_%d", (int) i
);
144 for (i
= 0; i
< idim1
; i
++)
145 fprintf (file
, " i1_%d", (int) i
);
146 for (i
= 0; i
< tdim2
; i
++)
147 fprintf (file
, " t2_%d", (int) i
);
148 for (i
= 0; i
< idim2
; i
++)
149 fprintf (file
, " i2_%d", (int) i
);
150 for (i
= 0; i
< sdim1
; i
++)
151 fprintf (file
, " s1_%d", (int) i
);
152 for (i
= 0; i
< sdim2
; i
++)
153 fprintf (file
, " s2_%d", (int) i
);
154 for (i
= 0; i
< gdim
; i
++)
155 fprintf (file
, " g_%d", (int) i
);
157 fprintf (file
, " cst\n");
160 /* Prints to FILE the poly_ddr_p PDDR. */
163 print_pddr (FILE *file
, poly_ddr_p pddr
)
165 fprintf (file
, "pddr (kind: ");
167 if (PDDR_KIND (pddr
) == unknown_dependence
)
168 fprintf (file
, "unknown_dependence");
169 else if (PDDR_KIND (pddr
) == no_dependence
)
170 fprintf (file
, "no_dependence");
171 else if (PDDR_KIND (pddr
) == has_dependence
)
172 fprintf (file
, "has_dependence");
174 fprintf (file
, "\n source ");
175 print_pdr (file
, PDDR_SOURCE (pddr
), 2);
177 fprintf (file
, "\n sink ");
178 print_pdr (file
, PDDR_SINK (pddr
), 2);
180 if (PDDR_KIND (pddr
) == has_dependence
)
182 fprintf (file
, "\n dependence polyhedron (\n");
183 print_dependence_polyhedron_layout (file
, pddr
);
184 ppl_print_powerset_matrix (file
, PDDR_DDP (pddr
));
185 ppl_io_fprint_Pointset_Powerset_C_Polyhedron (file
, PDDR_DDP (pddr
));
186 fprintf (file
, ")\n");
189 fprintf (file
, ")\n");
192 /* Prints to STDERR the poly_ddr_p PDDR. */
195 debug_pddr (poly_ddr_p pddr
)
197 print_pddr (stderr
, pddr
);
201 /* Remove all the dimensions except alias information at dimension
205 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset
,
206 ppl_dimension_type alias_dim
)
208 ppl_dimension_type
*ds
;
209 ppl_dimension_type access_dim
;
212 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset
,
214 ds
= XNEWVEC (ppl_dimension_type
, access_dim
-1);
215 for (i
= 0; i
< access_dim
; i
++)
224 ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset
,
230 /* Return true when PDR1 and PDR2 may alias. */
233 poly_drs_may_alias_p (poly_dr_p pdr1
, poly_dr_p pdr2
)
235 ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1
, alias_powerset2
;
236 ppl_Pointset_Powerset_C_Polyhedron_t accesses1
= PDR_ACCESSES (pdr1
);
237 ppl_Pointset_Powerset_C_Polyhedron_t accesses2
= PDR_ACCESSES (pdr2
);
238 ppl_dimension_type alias_dim1
= pdr_alias_set_dim (pdr1
);
239 ppl_dimension_type alias_dim2
= pdr_alias_set_dim (pdr2
);
242 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
243 (&alias_powerset1
, accesses1
);
244 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
245 (&alias_powerset2
, accesses2
);
247 build_alias_set_powerset (alias_powerset1
, alias_dim1
);
248 build_alias_set_powerset (alias_powerset2
, alias_dim2
);
250 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
251 (alias_powerset1
, alias_powerset2
);
253 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1
);
255 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1
);
256 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2
);
261 /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
262 transformed into "a CUT0 c CUT1' b"
264 Add NB0 zeros before "a": "00...0 a CUT0 c CUT1' b"
265 Add NB1 zeros between "a" and "c": "00...0 a 00...0 c CUT1' b"
266 Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b":
267 "00...0 a 00...0 c 00...0 b". */
269 static ppl_Pointset_Powerset_C_Polyhedron_t
270 map_dr_into_dep_poly (graphite_dim_t dim
,
271 ppl_Pointset_Powerset_C_Polyhedron_t dr
,
272 graphite_dim_t cut0
, graphite_dim_t cut1
,
273 graphite_dim_t nb0
, graphite_dim_t nb1
)
275 ppl_dimension_type pdim
;
276 ppl_dimension_type
*map
;
277 ppl_Pointset_Powerset_C_Polyhedron_t res
;
278 ppl_dimension_type i
;
280 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
282 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res
, &pdim
);
284 map
= (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, pdim
);
286 /* First mapping: move 'g' vector to right position. */
287 for (i
= 0; i
< cut0
; i
++)
290 for (i
= cut0
; i
< cut1
; i
++)
291 map
[i
] = pdim
- cut1
+ i
;
293 for (i
= cut1
; i
< pdim
; i
++)
294 map
[i
] = cut0
+ i
- cut1
;
296 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res
, map
, pdim
);
299 /* After swapping 's' and 'g' vectors, we have to update a new cut. */
300 cut1
= pdim
- cut1
+ cut0
;
302 ppl_insert_dimensions_pointset (res
, 0, nb0
);
303 ppl_insert_dimensions_pointset (res
, nb0
+ cut0
, nb1
);
304 ppl_insert_dimensions_pointset (res
, nb0
+ nb1
+ cut1
,
305 dim
- nb0
- nb1
- pdim
);
310 /* Builds subscript equality constraints. */
312 static ppl_Pointset_Powerset_C_Polyhedron_t
313 dr_equality_constraints (graphite_dim_t dim
,
314 graphite_dim_t pos
, graphite_dim_t nb_subscripts
)
316 ppl_Polyhedron_t eqs
;
317 ppl_Pointset_Powerset_C_Polyhedron_t res
;
320 ppl_new_C_Polyhedron_from_space_dimension (&eqs
, dim
, 0);
322 for (i
= 0; i
< nb_subscripts
; i
++)
324 ppl_Constraint_t cstr
325 = ppl_build_relation (dim
, pos
+ i
, pos
+ i
+ nb_subscripts
,
326 0, PPL_CONSTRAINT_TYPE_EQUAL
);
327 ppl_Polyhedron_add_constraint (eqs
, cstr
);
328 ppl_delete_Constraint (cstr
);
331 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, eqs
);
332 ppl_delete_Polyhedron (eqs
);
336 /* Builds scheduling inequality constraints: when DIRECTION is
337 1 builds a GE constraint,
338 0 builds an EQ constraint,
339 -1 builds a LE constraint.
340 DIM is the dimension of the scheduling space.
341 POS and POS + OFFSET are the dimensions that are related. */
343 static ppl_Pointset_Powerset_C_Polyhedron_t
344 build_pairwise_scheduling (graphite_dim_t dim
,
346 graphite_dim_t offset
,
349 ppl_Pointset_Powerset_C_Polyhedron_t res
;
350 ppl_Polyhedron_t equalities
;
351 ppl_Constraint_t cstr
;
352 graphite_dim_t a
= pos
;
353 graphite_dim_t b
= pos
+ offset
;
355 ppl_new_C_Polyhedron_from_space_dimension (&equalities
, dim
, 0);
360 /* Builds "a + 1 <= b. */
361 cstr
= ppl_build_relation (dim
, a
, b
, 1,
362 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
367 cstr
= ppl_build_relation (dim
, a
, b
, 0,
368 PPL_CONSTRAINT_TYPE_EQUAL
);
372 /* Builds "a >= b + 1. */
373 cstr
= ppl_build_relation (dim
, a
, b
, -1,
374 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
381 ppl_Polyhedron_add_constraint (equalities
, cstr
);
382 ppl_delete_Constraint (cstr
);
384 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, equalities
);
385 ppl_delete_Polyhedron (equalities
);
389 /* Add to a non empty polyhedron BAG the precedence constraints for
390 the lexicographical comparison of time vectors in BAG following the
391 lexicographical order. DIM is the dimension of the polyhedron BAG.
392 TDIM is the number of loops common to the two statements that are
393 compared lexicographically, i.e. the number of loops containing
394 both statements. OFFSET is the number of dimensions needed to
395 represent the first statement, i.e. dimT1 + dimI1 in the layout of
396 the BAG polyhedron: T1|I1|T2|I2|S1|S2|G. When DIRECTION is set to
397 1, compute the direct dependence from PDR1 to PDR2, and when
398 DIRECTION is -1, compute the reversed dependence relation, from
399 PDR2 to PDR1. GDIM is the number of parameters in the scop. */
401 static ppl_Pointset_Powerset_C_Polyhedron_t
402 build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag
,
405 graphite_dim_t offset
,
410 ppl_Pointset_Powerset_C_Polyhedron_t res
, lex
;
412 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res
, dim
, 1);
414 lex
= build_pairwise_scheduling (dim
, 0, offset
, direction
);
415 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex
, bag
);
417 if (!ppl_powerset_is_empty (lex
, gdim
))
418 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res
, lex
);
420 ppl_delete_Pointset_Powerset_C_Polyhedron (lex
);
422 for (i
= 0; i
< tdim
- 1; i
++)
424 ppl_Pointset_Powerset_C_Polyhedron_t sceq
;
426 sceq
= build_pairwise_scheduling (dim
, i
, offset
, 0);
427 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag
, sceq
);
428 ppl_delete_Pointset_Powerset_C_Polyhedron (sceq
);
430 if (ppl_powerset_is_empty (bag
, gdim
))
433 lex
= build_pairwise_scheduling (dim
, i
+ 1, offset
, direction
);
434 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex
, bag
);
436 if (!ppl_powerset_is_empty (lex
, gdim
))
437 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res
, lex
);
439 ppl_delete_Pointset_Powerset_C_Polyhedron (lex
);
445 /* Build the dependence polyhedron for data references PDR1 and PDR2.
446 The layout of the dependence polyhedron is:
451 | T1 and T2 the scattering dimensions for PDR1 and PDR2
452 | I1 and I2 the iteration domains
453 | S1 and S2 the subscripts
454 | G the global parameters.
456 When DIRECTION is set to 1, compute the direct dependence from PDR1
457 to PDR2, and when DIRECTION is -1, compute the reversed dependence
458 relation, from PDR2 to PDR1. */
460 static ppl_Pointset_Powerset_C_Polyhedron_t
461 dependence_polyhedron_1 (poly_dr_p pdr1
, poly_dr_p pdr2
,
462 int direction
, bool original_scattering_p
)
464 poly_bb_p pbb1
= PDR_PBB (pdr1
);
465 poly_bb_p pbb2
= PDR_PBB (pdr2
);
466 scop_p scop
= PBB_SCOP (pbb1
);
467 graphite_dim_t tdim1
= original_scattering_p
?
468 pbb_nb_scattering_orig (pbb1
) : pbb_nb_scattering_transform (pbb1
);
469 graphite_dim_t tdim2
= original_scattering_p
?
470 pbb_nb_scattering_orig (pbb2
) : pbb_nb_scattering_transform (pbb2
);
471 graphite_dim_t ddim1
= pbb_dim_iter_domain (pbb1
);
472 graphite_dim_t ddim2
= pbb_dim_iter_domain (pbb2
);
473 graphite_dim_t sdim1
= PDR_NB_SUBSCRIPTS (pdr1
) + 1;
474 graphite_dim_t sdim2
= PDR_NB_SUBSCRIPTS (pdr2
) + 1;
475 graphite_dim_t gdim
= scop_nb_params (scop
);
476 graphite_dim_t dim1
= pdr_dim (pdr1
);
477 graphite_dim_t dim2
= pdr_dim (pdr2
);
478 graphite_dim_t dim
= tdim1
+ tdim2
+ dim1
+ dim2
- gdim
;
479 ppl_Pointset_Powerset_C_Polyhedron_t res
;
480 ppl_Pointset_Powerset_C_Polyhedron_t idr1
, idr2
;
481 ppl_Pointset_Powerset_C_Polyhedron_t sc1
, sc2
, dreq
;
483 gcc_assert (PBB_SCOP (pbb1
) == PBB_SCOP (pbb2
));
485 combine_context_id_scat (&sc1
, pbb1
, original_scattering_p
);
486 combine_context_id_scat (&sc2
, pbb2
, original_scattering_p
);
488 ppl_insert_dimensions_pointset (sc1
, tdim1
+ ddim1
,
489 tdim2
+ ddim2
+ sdim1
+ sdim2
);
491 ppl_insert_dimensions_pointset (sc2
, 0, tdim1
+ ddim1
);
492 ppl_insert_dimensions_pointset (sc2
, tdim1
+ ddim1
+ tdim2
+ ddim2
,
495 idr1
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr1
), ddim1
, ddim1
+ gdim
,
496 tdim1
, tdim2
+ ddim2
);
497 idr2
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr2
), ddim2
, ddim2
+ gdim
,
498 tdim1
+ ddim1
+ tdim2
, sdim1
);
500 /* Now add the subscript equalities. */
501 dreq
= dr_equality_constraints (dim
, tdim1
+ ddim1
+ tdim2
+ ddim2
, sdim1
);
503 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res
, dim
, 0);
504 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, sc1
);
505 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, sc2
);
506 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr1
);
507 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr2
);
508 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, dreq
);
509 ppl_delete_Pointset_Powerset_C_Polyhedron (sc1
);
510 ppl_delete_Pointset_Powerset_C_Polyhedron (sc2
);
511 ppl_delete_Pointset_Powerset_C_Polyhedron (idr1
);
512 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2
);
513 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq
);
515 if (!ppl_powerset_is_empty (res
, gdim
))
517 ppl_Pointset_Powerset_C_Polyhedron_t lex
=
518 build_lexicographical_constraint (res
, dim
, MIN (tdim1
, tdim2
),
519 tdim1
+ ddim1
, gdim
, direction
);
520 ppl_delete_Pointset_Powerset_C_Polyhedron (res
);
527 /* Build the dependence polyhedron for data references PDR1 and PDR2.
528 If possible use already cached information.
530 When DIRECTION is set to 1, compute the direct dependence from PDR1
531 to PDR2, and when DIRECTION is -1, compute the reversed dependence
532 relation, from PDR2 to PDR1. */
535 dependence_polyhedron (poly_dr_p pdr1
, poly_dr_p pdr2
,
536 int direction
, bool original_scattering_p
)
540 ppl_Pointset_Powerset_C_Polyhedron_t ddp
;
542 /* Return the PDDR from the cache if it already has been computed. */
543 if (original_scattering_p
)
546 scop_p scop
= PBB_SCOP (PDR_PBB (pdr1
));
550 x
= htab_find_slot (SCOP_ORIGINAL_PDDRS (scop
),
554 return (poly_ddr_p
) *x
;
557 if ((pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
558 || PDR_BASE_OBJECT_SET (pdr1
) != PDR_BASE_OBJECT_SET (pdr2
)
559 || PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
)
560 || !poly_drs_may_alias_p (pdr1
, pdr2
))
563 ddp
= dependence_polyhedron_1 (pdr1
, pdr2
, direction
,
564 original_scattering_p
);
566 res
= new_poly_ddr (pdr1
, pdr2
, ddp
, original_scattering_p
);
568 if (!(pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
569 && PDR_BASE_OBJECT_SET (pdr1
) != PDR_BASE_OBJECT_SET (pdr2
)
570 && poly_drs_may_alias_p (pdr1
, pdr2
))
571 PDDR_KIND (res
) = unknown_dependence
;
573 if (original_scattering_p
)
579 /* Return true when the data dependence relation between the data
580 references PDR1 belonging to PBB1 and PDR2 is part of a
584 reduction_dr_1 (poly_bb_p pbb1
, poly_dr_p pdr1
, poly_dr_p pdr2
)
589 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr
)
590 if (PDR_TYPE (pdr
) == PDR_WRITE
)
593 return same_pdr_p (pdr
, pdr1
) && same_pdr_p (pdr
, pdr2
);
596 /* Return true when the data dependence relation between the data
597 references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
598 part of a reduction. */
601 reduction_dr_p (poly_dr_p pdr1
, poly_dr_p pdr2
)
603 poly_bb_p pbb1
= PDR_PBB (pdr1
);
604 poly_bb_p pbb2
= PDR_PBB (pdr2
);
606 if (PBB_IS_REDUCTION (pbb1
))
607 return reduction_dr_1 (pbb1
, pdr1
, pdr2
);
609 if (PBB_IS_REDUCTION (pbb2
))
610 return reduction_dr_1 (pbb2
, pdr2
, pdr1
);
615 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
616 and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
620 graphite_legal_transform_dr (poly_dr_p pdr1
, poly_dr_p pdr2
)
622 ppl_Pointset_Powerset_C_Polyhedron_t po
, pt
;
623 graphite_dim_t ddim1
, otdim1
, otdim2
, ttdim1
, ttdim2
;
624 ppl_Pointset_Powerset_C_Polyhedron_t po_temp
;
625 ppl_dimension_type pdim
;
627 poly_ddr_p opddr
, tpddr
;
628 poly_bb_p pbb1
, pbb2
;
630 if (reduction_dr_p (pdr1
, pdr2
))
633 /* We build the reverse dependence relation for the transformed
634 scattering, such that when we intersect it with the original PO,
635 we get an empty intersection when the transform is legal:
636 i.e. the transform should reverse no dependences, and so PT, the
637 reversed transformed PDDR, should have no constraint from PO. */
638 opddr
= dependence_polyhedron (pdr1
, pdr2
, 1, true);
640 if (PDDR_KIND (opddr
) == unknown_dependence
)
643 /* There are no dependences between PDR1 and PDR2 in the original
644 version of the program, or after the transform, so the
645 transform is legal. */
646 if (pddr_is_empty (opddr
))
649 tpddr
= dependence_polyhedron (pdr1
, pdr2
, -1, false);
651 if (PDDR_KIND (tpddr
) == unknown_dependence
)
653 free_poly_ddr (tpddr
);
657 if (pddr_is_empty (tpddr
))
659 free_poly_ddr (tpddr
);
663 po
= PDDR_DDP (opddr
);
664 pt
= PDDR_DDP (tpddr
);
666 /* Copy PO into PO_TEMP, such that PO is not destroyed. PO is
667 stored in a cache and should not be modified or freed. */
668 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po
, &pdim
);
669 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&po_temp
,
671 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp
, po
);
673 /* Extend PO and PT to have the same dimensions. */
674 pbb1
= PDR_PBB (pdr1
);
675 pbb2
= PDR_PBB (pdr2
);
676 ddim1
= pbb_dim_iter_domain (pbb1
);
677 otdim1
= pbb_nb_scattering_orig (pbb1
);
678 otdim2
= pbb_nb_scattering_orig (pbb2
);
679 ttdim1
= pbb_nb_scattering_transform (pbb1
);
680 ttdim2
= pbb_nb_scattering_transform (pbb2
);
681 ppl_insert_dimensions_pointset (po_temp
, otdim1
, ttdim1
);
682 ppl_insert_dimensions_pointset (po_temp
, otdim1
+ ttdim1
+ ddim1
+ otdim2
,
684 ppl_insert_dimensions_pointset (pt
, 0, otdim1
);
685 ppl_insert_dimensions_pointset (pt
, otdim1
+ ttdim1
+ ddim1
, otdim2
);
687 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp
, pt
);
688 is_empty_p
= ppl_powerset_is_empty (po_temp
,
689 scop_nb_params (PBB_SCOP (pbb1
)));
691 ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp
);
692 free_poly_ddr (tpddr
);
694 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
695 fprintf (dump_file
, "\nloop carries dependency.\n");
700 /* Return true when the data dependence relation for PBB1 and PBB2 is
701 part of a reduction. */
704 reduction_ddr_p (poly_bb_p pbb1
, poly_bb_p pbb2
)
706 return pbb1
== pbb2
&& PBB_IS_REDUCTION (pbb1
);
709 /* Iterates over the data references of PBB1 and PBB2 and detect
710 whether the transformed schedule is correct. */
713 graphite_legal_transform_bb (poly_bb_p pbb1
, poly_bb_p pbb2
)
716 poly_dr_p pdr1
, pdr2
;
718 if (!PBB_PDR_DUPLICATES_REMOVED (pbb1
))
719 pbb_remove_duplicate_pdrs (pbb1
);
721 if (!PBB_PDR_DUPLICATES_REMOVED (pbb2
))
722 pbb_remove_duplicate_pdrs (pbb2
);
724 if (reduction_ddr_p (pbb1
, pbb2
))
727 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
)
728 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
)
729 if (!graphite_legal_transform_dr (pdr1
, pdr2
))
735 /* Iterates over the SCOP and detect whether the transformed schedule
739 graphite_legal_transform (scop_p scop
)
742 poly_bb_p pbb1
, pbb2
;
744 timevar_push (TV_GRAPHITE_DATA_DEPS
);
746 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
747 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
748 if (!graphite_legal_transform_bb (pbb1
, pbb2
))
750 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
754 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
758 /* Returns TRUE when the dependence polyhedron between PDR1 and
759 PDR2 represents a loop carried dependence at level LEVEL. */
762 graphite_carried_dependence_level_k (poly_dr_p pdr1
, poly_dr_p pdr2
,
765 ppl_Pointset_Powerset_C_Polyhedron_t po
;
766 ppl_Pointset_Powerset_C_Polyhedron_t eqpp
;
767 graphite_dim_t tdim1
= pbb_nb_scattering_transform (PDR_PBB (pdr1
));
768 graphite_dim_t ddim1
= pbb_dim_iter_domain (PDR_PBB (pdr1
));
769 ppl_dimension_type dim
;
771 poly_ddr_p pddr
= dependence_polyhedron (pdr1
, pdr2
, 1, false);
773 if (PDDR_KIND (pddr
) == unknown_dependence
)
775 free_poly_ddr (pddr
);
779 if (pddr_is_empty (pddr
))
781 free_poly_ddr (pddr
);
785 po
= PDDR_DDP (pddr
);
786 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po
, &dim
);
787 eqpp
= build_pairwise_scheduling (dim
, level
, tdim1
+ ddim1
, 1);
789 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp
, po
);
790 empty_p
= ppl_powerset_is_empty
791 (eqpp
, scop_nb_params (PBB_SCOP (PDR_PBB (pdr1
))));
793 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp
);
794 free_poly_ddr (pddr
);
799 /* Check data dependency between PBB1 and PBB2 at level LEVEL. */
802 dependency_between_pbbs_p (poly_bb_p pbb1
, poly_bb_p pbb2
, int level
)
805 poly_dr_p pdr1
, pdr2
;
807 timevar_push (TV_GRAPHITE_DATA_DEPS
);
809 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
)
810 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
)
811 if (graphite_carried_dependence_level_k (pdr1
, pdr2
, level
))
813 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
817 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
821 /* Pretty print to FILE all the original data dependences of SCoP in
825 dot_original_deps_stmt_1 (FILE *file
, scop_p scop
)
828 poly_bb_p pbb1
, pbb2
;
829 poly_dr_p pdr1
, pdr2
;
831 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
832 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
834 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
)
835 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
)
836 if (!pddr_is_empty (dependence_polyhedron (pdr1
, pdr2
, 1, true)))
838 fprintf (file
, "OS%d -> OS%d\n",
839 pbb_index (pbb1
), pbb_index (pbb2
));
846 /* Pretty print to FILE all the transformed data dependences of SCoP in
850 dot_transformed_deps_stmt_1 (FILE *file
, scop_p scop
)
853 poly_bb_p pbb1
, pbb2
;
854 poly_dr_p pdr1
, pdr2
;
856 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
857 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
859 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
)
860 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
)
862 poly_ddr_p pddr
= dependence_polyhedron (pdr1
, pdr2
, 1, false);
864 if (!pddr_is_empty (pddr
))
866 fprintf (file
, "TS%d -> TS%d\n",
867 pbb_index (pbb1
), pbb_index (pbb2
));
869 free_poly_ddr (pddr
);
873 free_poly_ddr (pddr
);
880 /* Pretty print to FILE all the data dependences of SCoP in DOT
884 dot_deps_stmt_1 (FILE *file
, scop_p scop
)
886 fputs ("digraph all {\n", file
);
888 dot_original_deps_stmt_1 (file
, scop
);
889 dot_transformed_deps_stmt_1 (file
, scop
);
891 fputs ("}\n\n", file
);
894 /* Pretty print to FILE all the original data dependences of SCoP in
898 dot_original_deps (FILE *file
, scop_p scop
)
901 poly_bb_p pbb1
, pbb2
;
902 poly_dr_p pdr1
, pdr2
;
904 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
905 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
906 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
)
907 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
)
908 if (!pddr_is_empty (dependence_polyhedron (pdr1
, pdr2
, 1, true)))
909 fprintf (file
, "OS%d_D%d -> OS%d_D%d\n",
910 pbb_index (pbb1
), PDR_ID (pdr1
),
911 pbb_index (pbb2
), PDR_ID (pdr2
));
914 /* Pretty print to FILE all the transformed data dependences of SCoP in
918 dot_transformed_deps (FILE *file
, scop_p scop
)
921 poly_bb_p pbb1
, pbb2
;
922 poly_dr_p pdr1
, pdr2
;
924 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
925 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
926 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
)
927 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
)
929 poly_ddr_p pddr
= dependence_polyhedron (pdr1
, pdr2
, 1, false);
931 if (!pddr_is_empty (pddr
))
932 fprintf (file
, "TS%d_D%d -> TS%d_D%d\n",
933 pbb_index (pbb1
), PDR_ID (pdr1
),
934 pbb_index (pbb2
), PDR_ID (pdr2
));
936 free_poly_ddr (pddr
);
940 /* Pretty print to FILE all the data dependences of SCoP in DOT
944 dot_deps_1 (FILE *file
, scop_p scop
)
946 fputs ("digraph all {\n", file
);
948 dot_original_deps (file
, scop
);
949 dot_transformed_deps (file
, scop
);
951 fputs ("}\n\n", file
);
954 /* Display all the data dependences in SCoP using dotty. */
957 dot_deps (scop_p scop
)
959 /* When debugging, enable the following code. This cannot be used
960 in production compilers because it calls "system". */
962 FILE *stream
= fopen ("/tmp/scopdeps.dot", "w");
965 dot_deps_1 (stream
, scop
);
968 system ("dotty /tmp/scopdeps.dot &");
970 dot_deps_1 (stderr
, scop
);
974 /* Display all the statement dependences in SCoP using dotty. */
977 dot_deps_stmt (scop_p scop
)
979 /* When debugging, enable the following code. This cannot be used
980 in production compilers because it calls "system". */
982 FILE *stream
= fopen ("/tmp/scopdeps.dot", "w");
985 dot_deps_stmt_1 (stream
, scop
);
988 system ("dotty /tmp/scopdeps.dot &");
990 dot_deps_stmt_1 (stderr
, scop
);