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"
38 #include "graphite-cloog-util.h"
40 /* Comparison function for poly_ddr hash table. */
43 eq_poly_ddr_p (const void *pddr1
, const void *pddr2
)
45 const struct poly_ddr
*p1
= (const struct poly_ddr
*) pddr1
;
46 const struct poly_ddr
*p2
= (const struct poly_ddr
*) pddr2
;
48 return (PDDR_SOURCE (p1
) == PDDR_SOURCE (p2
)
49 && PDDR_SINK (p1
) == PDDR_SINK (p2
));
52 /* Hash function for poly_ddr hashtable. */
55 hash_poly_ddr_p (const void *pddr
)
57 const struct poly_ddr
*p
= (const struct poly_ddr
*) pddr
;
59 return (hashval_t
) ((long) PDDR_SOURCE (p
) + (long) PDDR_SINK (p
));
62 /* Returns true when PDDR has no dependence. */
65 pddr_is_empty (poly_ddr_p pddr
)
70 gcc_assert (PDDR_KIND (pddr
) != unknown_dependence
);
72 return PDDR_KIND (pddr
) == no_dependence
? true : false;
75 /* Prints to FILE the layout of the dependence polyhedron of PDDR:
80 | T1 and T2 the scattering dimensions for PDDR_SOURCE and PDDR_SINK
81 | I1 and I2 the iteration domains
82 | S1 and S2 the subscripts
83 | G the global parameters. */
86 print_dependence_polyhedron_layout (FILE *file
, poly_ddr_p pddr
)
88 poly_dr_p pdr1
= PDDR_SOURCE (pddr
);
89 poly_dr_p pdr2
= PDDR_SINK (pddr
);
90 poly_bb_p pbb1
= PDR_PBB (pdr1
);
91 poly_bb_p pbb2
= PDR_PBB (pdr2
);
94 graphite_dim_t tdim1
= PDDR_ORIGINAL_SCATTERING_P (pddr
) ?
95 pbb_nb_scattering_orig (pbb1
) : pbb_nb_scattering_transform (pbb1
);
96 graphite_dim_t tdim2
= PDDR_ORIGINAL_SCATTERING_P (pddr
) ?
97 pbb_nb_scattering_orig (pbb2
) : pbb_nb_scattering_transform (pbb2
);
98 graphite_dim_t idim1
= pbb_dim_iter_domain (pbb1
);
99 graphite_dim_t idim2
= pbb_dim_iter_domain (pbb2
);
100 graphite_dim_t sdim1
= PDR_NB_SUBSCRIPTS (pdr1
) + 1;
101 graphite_dim_t sdim2
= PDR_NB_SUBSCRIPTS (pdr2
) + 1;
102 graphite_dim_t gdim
= scop_nb_params (PBB_SCOP (pbb1
));
104 fprintf (file
, "# eq");
106 for (i
= 0; i
< tdim1
; i
++)
107 fprintf (file
, " t1_%d", (int) i
);
108 for (i
= 0; i
< idim1
; i
++)
109 fprintf (file
, " i1_%d", (int) i
);
110 for (i
= 0; i
< tdim2
; i
++)
111 fprintf (file
, " t2_%d", (int) i
);
112 for (i
= 0; i
< idim2
; i
++)
113 fprintf (file
, " i2_%d", (int) i
);
114 for (i
= 0; i
< sdim1
; i
++)
115 fprintf (file
, " s1_%d", (int) i
);
116 for (i
= 0; i
< sdim2
; i
++)
117 fprintf (file
, " s2_%d", (int) i
);
118 for (i
= 0; i
< gdim
; i
++)
119 fprintf (file
, " g_%d", (int) i
);
121 fprintf (file
, " cst\n");
124 /* Prints to FILE the poly_ddr_p PDDR. */
127 print_pddr (FILE *file
, poly_ddr_p pddr
)
129 fprintf (file
, "pddr (kind: ");
131 if (PDDR_KIND (pddr
) == unknown_dependence
)
132 fprintf (file
, "unknown_dependence");
133 else if (PDDR_KIND (pddr
) == no_dependence
)
134 fprintf (file
, "no_dependence");
135 else if (PDDR_KIND (pddr
) == has_dependence
)
136 fprintf (file
, "has_dependence");
138 fprintf (file
, "\n source ");
139 print_pdr (file
, PDDR_SOURCE (pddr
), 2);
141 fprintf (file
, "\n sink ");
142 print_pdr (file
, PDDR_SINK (pddr
), 2);
144 if (PDDR_KIND (pddr
) == has_dependence
)
146 fprintf (file
, "\n dependence polyhedron (\n");
147 print_dependence_polyhedron_layout (file
, pddr
);
148 ppl_print_powerset_matrix (file
, PDDR_DDP (pddr
));
149 ppl_io_fprint_Pointset_Powerset_C_Polyhedron (file
, PDDR_DDP (pddr
));
150 fprintf (file
, ")\n");
153 fprintf (file
, ")\n");
156 /* Prints to STDERR the poly_ddr_p PDDR. */
159 debug_pddr (poly_ddr_p pddr
)
161 print_pddr (stderr
, pddr
);
165 /* Remove all the dimensions except alias information at dimension
169 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset
,
170 ppl_dimension_type alias_dim
)
172 ppl_dimension_type
*ds
;
173 ppl_dimension_type access_dim
;
176 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset
,
178 ds
= XNEWVEC (ppl_dimension_type
, access_dim
- 1);
179 gcc_assert (alias_dim
< access_dim
);
181 for (pos
= 0, i
= 0; i
< access_dim
; i
++)
185 ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset
,
191 /* Return true when PDR1 and PDR2 may alias. */
194 poly_drs_may_alias_p (poly_dr_p pdr1
, poly_dr_p pdr2
)
196 ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1
, alias_powerset2
;
197 ppl_Pointset_Powerset_C_Polyhedron_t accesses1
= PDR_ACCESSES (pdr1
);
198 ppl_Pointset_Powerset_C_Polyhedron_t accesses2
= PDR_ACCESSES (pdr2
);
199 ppl_dimension_type alias_dim1
= pdr_alias_set_dim (pdr1
);
200 ppl_dimension_type alias_dim2
= pdr_alias_set_dim (pdr2
);
203 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
204 (&alias_powerset1
, accesses1
);
205 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
206 (&alias_powerset2
, accesses2
);
208 build_alias_set_powerset (alias_powerset1
, alias_dim1
);
209 build_alias_set_powerset (alias_powerset2
, alias_dim2
);
211 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
212 (alias_powerset1
, alias_powerset2
);
214 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1
);
216 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1
);
217 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2
);
222 /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
223 transformed into "a CUT0 c CUT1' b"
225 Add NB0 zeros before "a": "00...0 a CUT0 c CUT1' b"
226 Add NB1 zeros between "a" and "c": "00...0 a 00...0 c CUT1' b"
227 Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b":
228 "00...0 a 00...0 c 00...0 b". */
230 static ppl_Pointset_Powerset_C_Polyhedron_t
231 map_dr_into_dep_poly (graphite_dim_t dim
,
232 ppl_Pointset_Powerset_C_Polyhedron_t dr
,
233 graphite_dim_t cut0
, graphite_dim_t cut1
,
234 graphite_dim_t nb0
, graphite_dim_t nb1
)
236 ppl_dimension_type pdim
;
237 ppl_dimension_type
*map
;
238 ppl_Pointset_Powerset_C_Polyhedron_t res
;
239 ppl_dimension_type i
;
241 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
243 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res
, &pdim
);
245 map
= (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, pdim
);
247 /* First mapping: move 'g' vector to right position. */
248 for (i
= 0; i
< cut0
; i
++)
251 for (i
= cut0
; i
< cut1
; i
++)
252 map
[i
] = pdim
- cut1
+ i
;
254 for (i
= cut1
; i
< pdim
; i
++)
255 map
[i
] = cut0
+ i
- cut1
;
257 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res
, map
, pdim
);
260 /* After swapping 's' and 'g' vectors, we have to update a new cut. */
261 cut1
= pdim
- cut1
+ cut0
;
263 ppl_insert_dimensions_pointset (res
, 0, nb0
);
264 ppl_insert_dimensions_pointset (res
, nb0
+ cut0
, nb1
);
265 ppl_insert_dimensions_pointset (res
, nb0
+ nb1
+ cut1
,
266 dim
- nb0
- nb1
- pdim
);
271 /* Builds subscript equality constraints. */
273 static ppl_Pointset_Powerset_C_Polyhedron_t
274 dr_equality_constraints (graphite_dim_t dim
,
275 graphite_dim_t pos
, graphite_dim_t nb_subscripts
)
277 ppl_Polyhedron_t eqs
;
278 ppl_Pointset_Powerset_C_Polyhedron_t res
;
281 ppl_new_C_Polyhedron_from_space_dimension (&eqs
, dim
, 0);
283 for (i
= 0; i
< nb_subscripts
; i
++)
285 ppl_Constraint_t cstr
286 = ppl_build_relation (dim
, pos
+ i
, pos
+ i
+ nb_subscripts
,
287 0, PPL_CONSTRAINT_TYPE_EQUAL
);
288 ppl_Polyhedron_add_constraint (eqs
, cstr
);
289 ppl_delete_Constraint (cstr
);
292 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, eqs
);
293 ppl_delete_Polyhedron (eqs
);
297 /* Builds scheduling inequality constraints: when DIRECTION is
298 1 builds a GE constraint,
299 0 builds an EQ constraint,
300 -1 builds a LE constraint.
301 DIM is the dimension of the scheduling space.
302 POS and POS + OFFSET are the dimensions that are related. */
304 static ppl_Pointset_Powerset_C_Polyhedron_t
305 build_pairwise_scheduling (graphite_dim_t dim
,
307 graphite_dim_t offset
,
310 ppl_Pointset_Powerset_C_Polyhedron_t res
;
311 ppl_Polyhedron_t equalities
;
312 ppl_Constraint_t cstr
;
313 graphite_dim_t a
= pos
;
314 graphite_dim_t b
= pos
+ offset
;
316 ppl_new_C_Polyhedron_from_space_dimension (&equalities
, dim
, 0);
321 /* Builds "a + 1 <= b. */
322 cstr
= ppl_build_relation (dim
, a
, b
, 1,
323 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
328 cstr
= ppl_build_relation (dim
, a
, b
, 0,
329 PPL_CONSTRAINT_TYPE_EQUAL
);
333 /* Builds "a >= b + 1. */
334 cstr
= ppl_build_relation (dim
, a
, b
, -1,
335 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
342 ppl_Polyhedron_add_constraint (equalities
, cstr
);
343 ppl_delete_Constraint (cstr
);
345 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, equalities
);
346 ppl_delete_Polyhedron (equalities
);
350 /* Add to a non empty polyhedron BAG the precedence constraints for
351 the lexicographical comparison of time vectors in BAG following the
352 lexicographical order. DIM is the dimension of the polyhedron BAG.
353 TDIM is the number of loops common to the two statements that are
354 compared lexicographically, i.e. the number of loops containing
355 both statements. OFFSET is the number of dimensions needed to
356 represent the first statement, i.e. dimT1 + dimI1 in the layout of
357 the BAG polyhedron: T1|I1|T2|I2|S1|S2|G. When DIRECTION is set to
358 1, compute the direct dependence from PDR1 to PDR2, and when
359 DIRECTION is -1, compute the reversed dependence relation, from
362 static ppl_Pointset_Powerset_C_Polyhedron_t
363 build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag
,
366 graphite_dim_t offset
,
370 ppl_Pointset_Powerset_C_Polyhedron_t res
, lex
;
372 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res
, dim
, 1);
374 lex
= build_pairwise_scheduling (dim
, 0, offset
, direction
);
375 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex
, bag
);
377 if (!ppl_powerset_is_empty (lex
))
378 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res
, lex
);
380 ppl_delete_Pointset_Powerset_C_Polyhedron (lex
);
382 for (i
= 0; i
< tdim
- 1; i
++)
384 ppl_Pointset_Powerset_C_Polyhedron_t sceq
;
386 sceq
= build_pairwise_scheduling (dim
, i
, offset
, 0);
387 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag
, sceq
);
388 ppl_delete_Pointset_Powerset_C_Polyhedron (sceq
);
390 if (ppl_powerset_is_empty (bag
))
393 lex
= build_pairwise_scheduling (dim
, i
+ 1, offset
, direction
);
394 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex
, bag
);
396 if (!ppl_powerset_is_empty (lex
))
397 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res
, lex
);
399 ppl_delete_Pointset_Powerset_C_Polyhedron (lex
);
405 /* Build the dependence polyhedron for data references PDR1 and PDR2.
406 The layout of the dependence polyhedron is:
411 | T1 and T2 the scattering dimensions for PDR1 and PDR2
412 | I1 and I2 the iteration domains
413 | S1 and S2 the subscripts
414 | G the global parameters.
416 When DIRECTION is set to 1, compute the direct dependence from PDR1
417 to PDR2, and when DIRECTION is -1, compute the reversed dependence
418 relation, from PDR2 to PDR1. */
420 static ppl_Pointset_Powerset_C_Polyhedron_t
421 dependence_polyhedron (poly_dr_p pdr1
, poly_dr_p pdr2
,
422 int direction
, bool original_scattering_p
)
424 poly_bb_p pbb1
= PDR_PBB (pdr1
);
425 poly_bb_p pbb2
= PDR_PBB (pdr2
);
426 scop_p scop
= PBB_SCOP (pbb1
);
427 graphite_dim_t tdim1
= original_scattering_p
?
428 pbb_nb_scattering_orig (pbb1
) : pbb_nb_scattering_transform (pbb1
);
429 graphite_dim_t tdim2
= original_scattering_p
?
430 pbb_nb_scattering_orig (pbb2
) : pbb_nb_scattering_transform (pbb2
);
431 graphite_dim_t ddim1
= pbb_dim_iter_domain (pbb1
);
432 graphite_dim_t ddim2
= pbb_dim_iter_domain (pbb2
);
433 graphite_dim_t sdim1
= PDR_NB_SUBSCRIPTS (pdr1
) + 1;
434 graphite_dim_t sdim2
= PDR_NB_SUBSCRIPTS (pdr2
) + 1;
435 graphite_dim_t gdim
= scop_nb_params (scop
);
436 graphite_dim_t dim1
= pdr_dim (pdr1
);
437 graphite_dim_t dim2
= pdr_dim (pdr2
);
438 graphite_dim_t dim
= tdim1
+ tdim2
+ dim1
+ dim2
- gdim
;
439 ppl_Pointset_Powerset_C_Polyhedron_t res
;
440 ppl_Pointset_Powerset_C_Polyhedron_t idr1
, idr2
;
441 ppl_Pointset_Powerset_C_Polyhedron_t sc1
, sc2
, dreq
;
442 ppl_Pointset_Powerset_C_Polyhedron_t lex
;
444 gcc_assert (PBB_SCOP (pbb1
) == PBB_SCOP (pbb2
));
446 combine_context_id_scat (&sc1
, pbb1
, original_scattering_p
);
447 combine_context_id_scat (&sc2
, pbb2
, original_scattering_p
);
449 ppl_insert_dimensions_pointset (sc1
, tdim1
+ ddim1
,
450 tdim2
+ ddim2
+ sdim1
+ sdim2
);
452 ppl_insert_dimensions_pointset (sc2
, 0, tdim1
+ ddim1
);
453 ppl_insert_dimensions_pointset (sc2
, tdim1
+ ddim1
+ tdim2
+ ddim2
,
456 idr1
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr1
), ddim1
, ddim1
+ gdim
,
457 tdim1
, tdim2
+ ddim2
);
458 idr2
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr2
), ddim2
, ddim2
+ gdim
,
459 tdim1
+ ddim1
+ tdim2
, sdim1
);
461 /* Now add the subscript equalities. */
462 dreq
= dr_equality_constraints (dim
, tdim1
+ ddim1
+ tdim2
+ ddim2
, sdim1
);
464 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res
, dim
, 0);
465 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, sc1
);
466 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, sc2
);
467 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr1
);
468 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr2
);
469 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, dreq
);
470 ppl_delete_Pointset_Powerset_C_Polyhedron (sc1
);
471 ppl_delete_Pointset_Powerset_C_Polyhedron (sc2
);
472 ppl_delete_Pointset_Powerset_C_Polyhedron (idr1
);
473 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2
);
474 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq
);
476 if (ppl_powerset_is_empty (res
))
479 lex
= build_lexicographical_constraint (res
, dim
, MIN (tdim1
, tdim2
),
480 tdim1
+ ddim1
, direction
);
481 ppl_delete_Pointset_Powerset_C_Polyhedron (res
);
486 /* Build the dependence polyhedron for data references PDR1 and PDR2.
487 If possible use already cached information.
489 When DIRECTION is set to 1, compute the direct dependence from PDR1
490 to PDR2, and when DIRECTION is -1, compute the reversed dependence
491 relation, from PDR2 to PDR1. */
494 new_poly_ddr (poly_dr_p pdr1
, poly_dr_p pdr2
,
495 int direction
, bool original_scattering_p
)
501 /* Return the PDDR from the cache if it already has been computed. */
502 if (original_scattering_p
)
505 scop_p scop
= PBB_SCOP (PDR_PBB (pdr1
));
509 x
= htab_find_slot (SCOP_ORIGINAL_PDDRS (scop
),
513 return (poly_ddr_p
) *x
;
516 res
= XNEW (struct poly_ddr
);
517 PDDR_SOURCE (res
) = pdr1
;
518 PDDR_SINK (res
) = pdr2
;
519 PDDR_DDP (res
) = NULL
;
520 PDDR_ORIGINAL_SCATTERING_P (res
) = original_scattering_p
;
521 PDDR_KIND (res
) = unknown_dependence
;
523 may_alias
= poly_drs_may_alias_p (pdr1
, pdr2
);
525 if (!(pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
526 && PDR_BASE_OBJECT_SET (pdr1
) != PDR_BASE_OBJECT_SET (pdr2
)
528 PDDR_KIND (res
) = unknown_dependence
;
530 else if (!(pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
531 && same_pdr_p (pdr1
, pdr2
)
534 PDDR_DDP (res
) = dependence_polyhedron (pdr1
, pdr2
, direction
,
535 original_scattering_p
);
537 PDDR_KIND (res
) = has_dependence
;
539 PDDR_KIND (res
) = no_dependence
;
542 PDDR_KIND (res
) = no_dependence
;
544 if (original_scattering_p
)
550 /* Free the data dependence relation poly_ddr_p P. */
553 free_poly_ddr (void *p
)
555 poly_ddr_p pddr
= (poly_ddr_p
) p
;
556 ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr
));
560 /* Return true when the data dependence relation between the data
561 references PDR1 belonging to PBB1 and PDR2 is part of a
565 reduction_dr_1 (poly_bb_p pbb1
, poly_dr_p pdr1
, poly_dr_p pdr2
)
570 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr
)
571 if (PDR_TYPE (pdr
) == PDR_WRITE
572 && same_pdr_p (pdr
, pdr1
) && same_pdr_p (pdr
, pdr2
))
578 /* Return true when the data dependence relation between the data
579 references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
580 part of a reduction. */
583 reduction_dr_p (poly_dr_p pdr1
, poly_dr_p pdr2
)
585 poly_bb_p pbb1
= PDR_PBB (pdr1
);
586 poly_bb_p pbb2
= PDR_PBB (pdr2
);
588 if (PBB_IS_REDUCTION (pbb1
))
589 return reduction_dr_1 (pbb1
, pdr1
, pdr2
);
591 if (PBB_IS_REDUCTION (pbb2
))
592 return reduction_dr_1 (pbb2
, pdr2
, pdr1
);
597 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
598 and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
602 graphite_legal_transform_dr (poly_dr_p pdr1
, poly_dr_p pdr2
)
604 ppl_Pointset_Powerset_C_Polyhedron_t po
, pt
;
605 graphite_dim_t ddim1
, otdim1
, otdim2
, ttdim1
, ttdim2
;
606 ppl_Pointset_Powerset_C_Polyhedron_t po_temp
;
607 ppl_dimension_type pdim
;
609 poly_ddr_p opddr
, tpddr
;
610 poly_bb_p pbb1
, pbb2
;
612 if (reduction_dr_p (pdr1
, pdr2
))
615 /* We build the reverse dependence relation for the transformed
616 scattering, such that when we intersect it with the original PO,
617 we get an empty intersection when the transform is legal:
618 i.e. the transform should reverse no dependences, and so PT, the
619 reversed transformed PDDR, should have no constraint from PO. */
620 opddr
= new_poly_ddr (pdr1
, pdr2
, 1, true);
622 if (PDDR_KIND (opddr
) == unknown_dependence
)
625 /* There are no dependences between PDR1 and PDR2 in the original
626 version of the program, or after the transform, so the
627 transform is legal. */
628 if (pddr_is_empty (opddr
))
631 tpddr
= new_poly_ddr (pdr1
, pdr2
, -1, false);
633 if (PDDR_KIND (tpddr
) == unknown_dependence
)
635 free_poly_ddr (tpddr
);
639 if (pddr_is_empty (tpddr
))
641 free_poly_ddr (tpddr
);
645 po
= PDDR_DDP (opddr
);
646 pt
= PDDR_DDP (tpddr
);
648 /* Copy PO into PO_TEMP, such that PO is not destroyed. PO is
649 stored in a cache and should not be modified or freed. */
650 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po
, &pdim
);
651 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&po_temp
,
653 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp
, po
);
655 /* Extend PO and PT to have the same dimensions. */
656 pbb1
= PDR_PBB (pdr1
);
657 pbb2
= PDR_PBB (pdr2
);
658 ddim1
= pbb_dim_iter_domain (pbb1
);
659 otdim1
= pbb_nb_scattering_orig (pbb1
);
660 otdim2
= pbb_nb_scattering_orig (pbb2
);
661 ttdim1
= pbb_nb_scattering_transform (pbb1
);
662 ttdim2
= pbb_nb_scattering_transform (pbb2
);
663 ppl_insert_dimensions_pointset (po_temp
, otdim1
, ttdim1
);
664 ppl_insert_dimensions_pointset (po_temp
, otdim1
+ ttdim1
+ ddim1
+ otdim2
,
666 ppl_insert_dimensions_pointset (pt
, 0, otdim1
);
667 ppl_insert_dimensions_pointset (pt
, otdim1
+ ttdim1
+ ddim1
, otdim2
);
669 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp
, pt
);
670 is_empty_p
= ppl_powerset_is_empty (po_temp
);
672 ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp
);
673 free_poly_ddr (tpddr
);
675 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
676 fprintf (dump_file
, "\nloop carries dependency.\n");
681 /* Return true when the data dependence relation for PBB1 and PBB2 is
682 part of a reduction. */
685 reduction_ddr_p (poly_bb_p pbb1
, poly_bb_p pbb2
)
687 return pbb1
== pbb2
&& PBB_IS_REDUCTION (pbb1
);
690 /* Iterates over the data references of PBB1 and PBB2 and detect
691 whether the transformed schedule is correct. */
694 graphite_legal_transform_bb (poly_bb_p pbb1
, poly_bb_p pbb2
)
697 poly_dr_p pdr1
, pdr2
;
699 if (!PBB_PDR_DUPLICATES_REMOVED (pbb1
))
700 pbb_remove_duplicate_pdrs (pbb1
);
702 if (!PBB_PDR_DUPLICATES_REMOVED (pbb2
))
703 pbb_remove_duplicate_pdrs (pbb2
);
705 if (reduction_ddr_p (pbb1
, pbb2
))
708 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
)
709 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
)
710 if (!graphite_legal_transform_dr (pdr1
, pdr2
))
716 /* Iterates over the SCOP and detect whether the transformed schedule
720 graphite_legal_transform (scop_p scop
)
723 poly_bb_p pbb1
, pbb2
;
725 timevar_push (TV_GRAPHITE_DATA_DEPS
);
727 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
728 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
729 if (!graphite_legal_transform_bb (pbb1
, pbb2
))
731 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
735 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
739 /* Returns TRUE when the dependence polyhedron between PDR1 and
740 PDR2 represents a loop carried dependence at level LEVEL. */
743 graphite_carried_dependence_level_k (poly_dr_p pdr1
, poly_dr_p pdr2
,
746 ppl_Pointset_Powerset_C_Polyhedron_t po
;
747 ppl_Pointset_Powerset_C_Polyhedron_t eqpp
;
748 graphite_dim_t tdim1
= pbb_nb_scattering_transform (PDR_PBB (pdr1
));
749 graphite_dim_t ddim1
= pbb_dim_iter_domain (PDR_PBB (pdr1
));
750 ppl_dimension_type dim
;
752 poly_ddr_p pddr
= new_poly_ddr (pdr1
, pdr2
, 1, false);
754 if (PDDR_KIND (pddr
) == unknown_dependence
)
756 free_poly_ddr (pddr
);
760 if (pddr_is_empty (pddr
))
762 free_poly_ddr (pddr
);
766 po
= PDDR_DDP (pddr
);
767 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po
, &dim
);
768 eqpp
= build_pairwise_scheduling (dim
, level
, tdim1
+ ddim1
, 1);
770 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp
, po
);
771 empty_p
= ppl_powerset_is_empty (eqpp
);
773 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp
);
774 free_poly_ddr (pddr
);
779 /* Check data dependency between PBB1 and PBB2 at level LEVEL. */
782 dependency_between_pbbs_p (poly_bb_p pbb1
, poly_bb_p pbb2
, int level
)
785 poly_dr_p pdr1
, pdr2
;
787 timevar_push (TV_GRAPHITE_DATA_DEPS
);
789 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
)
790 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
)
791 if (graphite_carried_dependence_level_k (pdr1
, pdr2
, level
))
793 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
797 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
801 /* When ORIG is true, pretty print to FILE all the original data
802 dependences of SCoP in DOT format, otherwise print the transformed
806 dot_deps_stmt_2 (FILE *file
, scop_p scop
, bool orig
)
809 poly_bb_p pbb1
, pbb2
;
810 poly_dr_p pdr1
, pdr2
;
812 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
813 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
815 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
)
816 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
)
818 poly_ddr_p pddr
= new_poly_ddr (pdr1
, pdr2
, 1, orig
);
820 if (!pddr_is_empty (pddr
))
822 fprintf (file
, orig
? "OS%d -> OS%d\n" : "TS%d -> TS%d\n",
823 pbb_index (pbb1
), pbb_index (pbb2
));
825 free_poly_ddr (pddr
);
829 free_poly_ddr (pddr
);
835 /* Pretty print to FILE all the data dependences of SCoP in DOT
839 dot_deps_stmt_1 (FILE *file
, scop_p scop
)
841 fputs ("digraph all {\n", file
);
843 dot_deps_stmt_2 (file
, scop
, true);
844 dot_deps_stmt_2 (file
, scop
, false);
846 fputs ("}\n\n", file
);
849 /* When ORIG is true, pretty print to FILE all the original data
850 dependences of SCoP in DOT format, otherwise print the transformed
854 dot_deps_2 (FILE *file
, scop_p scop
, bool orig
)
857 poly_bb_p pbb1
, pbb2
;
858 poly_dr_p pdr1
, pdr2
;
860 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
861 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
862 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
)
863 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
)
865 poly_ddr_p pddr
= new_poly_ddr (pdr1
, pdr2
, 1, orig
);
867 if (!pddr_is_empty (pddr
))
869 ? "OS%d_D%d -> OS%d_D%d\n" : "TS%d_D%d -> TS%d_D%d\n",
870 pbb_index (pbb1
), PDR_ID (pdr1
),
871 pbb_index (pbb2
), PDR_ID (pdr2
));
873 free_poly_ddr (pddr
);
877 /* Pretty print to FILE all the data dependences of SCoP in DOT
881 dot_deps_1 (FILE *file
, scop_p scop
)
883 fputs ("digraph all {\n", file
);
885 dot_deps_2 (file
, scop
, true);
886 dot_deps_2 (file
, scop
, false);
888 fputs ("}\n\n", file
);
891 /* Display all the data dependences in SCoP using dotty. */
894 dot_deps (scop_p scop
)
896 /* When debugging, enable the following code. This cannot be used
897 in production compilers because it calls "system". */
899 FILE *stream
= fopen ("/tmp/scopdeps.dot", "w");
902 dot_deps_1 (stream
, scop
);
905 system ("dotty /tmp/scopdeps.dot &");
907 dot_deps_1 (stderr
, scop
);
911 /* Display all the statement dependences in SCoP using dotty. */
914 dot_deps_stmt (scop_p scop
)
916 /* When debugging, enable the following code. This cannot be used
917 in production compilers because it calls "system". */
919 FILE *stream
= fopen ("/tmp/scopdeps.dot", "w");
922 dot_deps_stmt_1 (stream
, scop
);
925 system ("dotty /tmp/scopdeps.dot &");
927 dot_deps_stmt_1 (stderr
, scop
);