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
;
56 if (!ddp
|| ppl_Pointset_Powerset_C_Polyhedron_is_empty (ddp
))
57 PDDR_KIND (pddr
) = no_dependence
;
59 PDDR_KIND (pddr
) = has_dependence
;
64 /* Free the poly_ddr_p P. */
67 free_poly_ddr (void *p
)
69 poly_ddr_p pddr
= (poly_ddr_p
) p
;
70 ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr
));
74 /* Comparison function for poly_ddr hash table. */
77 eq_poly_ddr_p (const void *pddr1
, const void *pddr2
)
79 const struct poly_ddr
*p1
= (const struct poly_ddr
*) pddr1
;
80 const struct poly_ddr
*p2
= (const struct poly_ddr
*) pddr2
;
82 return (PDDR_SOURCE (p1
) == PDDR_SOURCE (p2
)
83 && PDDR_SINK (p1
) == PDDR_SINK (p2
));
86 /* Hash function for poly_ddr hashtable. */
89 hash_poly_ddr_p (const void *pddr
)
91 const struct poly_ddr
*p
= (const struct poly_ddr
*) pddr
;
93 return (hashval_t
) ((long) PDDR_SOURCE (p
) + (long) PDDR_SINK (p
));
96 /* Returns true when PDDR has no dependence. */
99 pddr_is_empty (poly_ddr_p pddr
)
104 gcc_assert (PDDR_KIND (pddr
) != unknown_dependence
);
106 return PDDR_KIND (pddr
) == no_dependence
? true : false;
109 /* Prints to FILE the layout of the dependence polyhedron of PDDR:
114 | T1 and T2 the scattering dimensions for PDDR_SOURCE and PDDR_SINK
115 | I1 and I2 the iteration domains
116 | S1 and S2 the subscripts
117 | G the global parameters. */
120 print_dependence_polyhedron_layout (FILE *file
, poly_ddr_p pddr
)
122 poly_dr_p pdr1
= PDDR_SOURCE (pddr
);
123 poly_dr_p pdr2
= PDDR_SINK (pddr
);
124 poly_bb_p pbb1
= PDR_PBB (pdr1
);
125 poly_bb_p pbb2
= PDR_PBB (pdr2
);
128 graphite_dim_t tdim1
= PDDR_ORIGINAL_SCATTERING_P (pddr
) ?
129 pbb_nb_scattering_orig (pbb1
) : pbb_nb_scattering_transform (pbb1
);
130 graphite_dim_t tdim2
= PDDR_ORIGINAL_SCATTERING_P (pddr
) ?
131 pbb_nb_scattering_orig (pbb2
) : pbb_nb_scattering_transform (pbb2
);
132 graphite_dim_t idim1
= pbb_dim_iter_domain (pbb1
);
133 graphite_dim_t idim2
= pbb_dim_iter_domain (pbb2
);
134 graphite_dim_t sdim1
= PDR_NB_SUBSCRIPTS (pdr1
) + 1;
135 graphite_dim_t sdim2
= PDR_NB_SUBSCRIPTS (pdr2
) + 1;
136 graphite_dim_t gdim
= scop_nb_params (PBB_SCOP (pbb1
));
138 fprintf (file
, "# eq");
140 for (i
= 0; i
< tdim1
; i
++)
141 fprintf (file
, " t1_%d", (int) i
);
142 for (i
= 0; i
< idim1
; i
++)
143 fprintf (file
, " i1_%d", (int) i
);
144 for (i
= 0; i
< tdim2
; i
++)
145 fprintf (file
, " t2_%d", (int) i
);
146 for (i
= 0; i
< idim2
; i
++)
147 fprintf (file
, " i2_%d", (int) i
);
148 for (i
= 0; i
< sdim1
; i
++)
149 fprintf (file
, " s1_%d", (int) i
);
150 for (i
= 0; i
< sdim2
; i
++)
151 fprintf (file
, " s2_%d", (int) i
);
152 for (i
= 0; i
< gdim
; i
++)
153 fprintf (file
, " g_%d", (int) i
);
155 fprintf (file
, " cst\n");
158 /* Prints to FILE the poly_ddr_p PDDR. */
161 print_pddr (FILE *file
, poly_ddr_p pddr
)
163 fprintf (file
, "pddr (kind: ");
165 if (PDDR_KIND (pddr
) == unknown_dependence
)
166 fprintf (file
, "unknown_dependence");
167 else if (PDDR_KIND (pddr
) == no_dependence
)
168 fprintf (file
, "no_dependence");
169 else if (PDDR_KIND (pddr
) == has_dependence
)
170 fprintf (file
, "has_dependence");
172 fprintf (file
, "\n source ");
173 print_pdr (file
, PDDR_SOURCE (pddr
), 2);
175 fprintf (file
, "\n sink ");
176 print_pdr (file
, PDDR_SINK (pddr
), 2);
178 if (PDDR_KIND (pddr
) == has_dependence
)
180 fprintf (file
, "\n dependence polyhedron (\n");
181 print_dependence_polyhedron_layout (file
, pddr
);
182 ppl_print_powerset_matrix (file
, PDDR_DDP (pddr
));
183 fprintf (file
, ")\n");
186 fprintf (file
, ")\n");
189 /* Prints to STDERR the poly_ddr_p PDDR. */
192 debug_pddr (poly_ddr_p pddr
)
194 print_pddr (stderr
, pddr
);
198 /* Remove all the dimensions except alias information at dimension
202 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset
,
203 ppl_dimension_type alias_dim
)
205 ppl_dimension_type
*ds
;
206 ppl_dimension_type access_dim
;
209 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset
,
211 ds
= XNEWVEC (ppl_dimension_type
, access_dim
-1);
212 for (i
= 0; i
< access_dim
; i
++)
221 ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset
,
227 /* Return true when PDR1 and PDR2 may alias. */
230 poly_drs_may_alias_p (poly_dr_p pdr1
, poly_dr_p pdr2
)
232 ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1
, alias_powerset2
;
233 ppl_Pointset_Powerset_C_Polyhedron_t accesses1
= PDR_ACCESSES (pdr1
);
234 ppl_Pointset_Powerset_C_Polyhedron_t accesses2
= PDR_ACCESSES (pdr2
);
235 ppl_dimension_type alias_dim1
= pdr_alias_set_dim (pdr1
);
236 ppl_dimension_type alias_dim2
= pdr_alias_set_dim (pdr2
);
239 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
240 (&alias_powerset1
, accesses1
);
241 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
242 (&alias_powerset2
, accesses2
);
244 build_alias_set_powerset (alias_powerset1
, alias_dim1
);
245 build_alias_set_powerset (alias_powerset2
, alias_dim2
);
247 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
248 (alias_powerset1
, alias_powerset2
);
250 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1
);
252 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1
);
253 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2
);
258 /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
259 transformed into "a CUT0 c CUT1' b"
261 Add NB0 zeros before "a": "00...0 a CUT0 c CUT1' b"
262 Add NB1 zeros between "a" and "c": "00...0 a 00...0 c CUT1' b"
263 Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b":
264 "00...0 a 00...0 c 00...0 b". */
266 static ppl_Pointset_Powerset_C_Polyhedron_t
267 map_dr_into_dep_poly (graphite_dim_t dim
,
268 ppl_Pointset_Powerset_C_Polyhedron_t dr
,
269 graphite_dim_t cut0
, graphite_dim_t cut1
,
270 graphite_dim_t nb0
, graphite_dim_t nb1
)
272 ppl_dimension_type pdim
;
273 ppl_dimension_type
*map
;
274 ppl_Pointset_Powerset_C_Polyhedron_t res
;
275 ppl_dimension_type i
;
277 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
279 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res
, &pdim
);
281 map
= (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, pdim
);
283 /* First mapping: move 'g' vector to right position. */
284 for (i
= 0; i
< cut0
; i
++)
287 for (i
= cut0
; i
< cut1
; i
++)
288 map
[i
] = pdim
- cut1
+ i
;
290 for (i
= cut1
; i
< pdim
; i
++)
291 map
[i
] = cut0
+ i
- cut1
;
293 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res
, map
, pdim
);
296 /* After swapping 's' and 'g' vectors, we have to update a new cut. */
297 cut1
= pdim
- cut1
+ cut0
;
299 ppl_insert_dimensions_pointset (res
, 0, nb0
);
300 ppl_insert_dimensions_pointset (res
, nb0
+ cut0
, nb1
);
301 ppl_insert_dimensions_pointset (res
, nb0
+ nb1
+ cut1
,
302 dim
- nb0
- nb1
- pdim
);
307 /* Builds subscript equality constraints. */
309 static ppl_Pointset_Powerset_C_Polyhedron_t
310 dr_equality_constraints (graphite_dim_t dim
,
311 graphite_dim_t pos
, graphite_dim_t nb_subscripts
)
313 ppl_Polyhedron_t eqs
;
314 ppl_Pointset_Powerset_C_Polyhedron_t res
;
317 ppl_new_C_Polyhedron_from_space_dimension (&eqs
, dim
, 0);
319 for (i
= 0; i
< nb_subscripts
; i
++)
321 ppl_Constraint_t cstr
322 = ppl_build_relation (dim
, pos
+ i
, pos
+ i
+ nb_subscripts
,
323 0, PPL_CONSTRAINT_TYPE_EQUAL
);
324 ppl_Polyhedron_add_constraint (eqs
, cstr
);
325 ppl_delete_Constraint (cstr
);
328 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, eqs
);
329 ppl_delete_Polyhedron (eqs
);
333 /* Builds scheduling inequality constraints: when DIRECTION is
334 1 builds a GE constraint,
335 0 builds an EQ constraint,
336 -1 builds a LE constraint. */
338 static ppl_Pointset_Powerset_C_Polyhedron_t
339 build_pairwise_scheduling (graphite_dim_t dim
,
341 graphite_dim_t offset
,
344 ppl_Pointset_Powerset_C_Polyhedron_t res
;
345 ppl_Polyhedron_t equalities
;
346 ppl_Constraint_t cstr
;
348 ppl_new_C_Polyhedron_from_space_dimension (&equalities
, dim
, 0);
353 cstr
= ppl_build_relation (dim
, pos
, pos
+ offset
, 1,
354 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
358 cstr
= ppl_build_relation (dim
, pos
, pos
+ offset
, 0,
359 PPL_CONSTRAINT_TYPE_EQUAL
);
363 cstr
= ppl_build_relation (dim
, pos
, pos
+ offset
, -1,
364 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
371 ppl_Polyhedron_add_constraint (equalities
, cstr
);
372 ppl_delete_Constraint (cstr
);
374 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, equalities
);
375 ppl_delete_Polyhedron (equalities
);
379 /* Add to a non empty polyhedron BAG the precedence constraints for
380 the lexicographical comparison of time vectors in BAG following the
381 lexicographical order. DIM is the dimension of the polyhedron BAG.
382 TDIM is the number of loops common to the two statements that are
383 compared lexicographically, i.e. the number of loops containing
384 both statements. OFFSET is the number of dimensions needed to
385 represent the first statement, i.e. dimT1 + dimI1 in the layout of
386 the BAG polyhedron: T1|I1|T2|I2|S1|S2|G. When DIRECTION is set to
387 1, compute the direct dependence from PDR1 to PDR2, and when
388 DIRECTION is -1, compute the reversed dependence relation, from
391 static ppl_Pointset_Powerset_C_Polyhedron_t
392 build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag
,
395 graphite_dim_t offset
,
399 ppl_Pointset_Powerset_C_Polyhedron_t res
, lex
;
401 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res
, dim
, 1);
403 lex
= build_pairwise_scheduling (dim
, 0, offset
, direction
);
404 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex
, bag
);
406 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex
))
407 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res
, lex
);
409 ppl_delete_Pointset_Powerset_C_Polyhedron (lex
);
411 for (i
= 0; i
< tdim
- 1; i
++)
413 ppl_Pointset_Powerset_C_Polyhedron_t sceq
;
415 sceq
= build_pairwise_scheduling (dim
, i
, offset
, 0);
416 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag
, sceq
);
417 ppl_delete_Pointset_Powerset_C_Polyhedron (sceq
);
419 lex
= build_pairwise_scheduling (dim
, i
+ 1, offset
, direction
);
420 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex
, bag
);
422 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex
))
423 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res
, lex
);
425 ppl_delete_Pointset_Powerset_C_Polyhedron (lex
);
431 /* Build the dependence polyhedron for data references PDR1 and PDR2.
432 The layout of the dependence polyhedron is:
437 | T1 and T2 the scattering dimensions for PDR1 and PDR2
438 | I1 and I2 the iteration domains
439 | S1 and S2 the subscripts
440 | G the global parameters.
442 When DIRECTION is set to 1, compute the direct dependence from PDR1
443 to PDR2, and when DIRECTION is -1, compute the reversed dependence
444 relation, from PDR2 to PDR1. */
446 static ppl_Pointset_Powerset_C_Polyhedron_t
447 dependence_polyhedron_1 (poly_dr_p pdr1
, poly_dr_p pdr2
,
448 int direction
, bool original_scattering_p
)
450 poly_bb_p pbb1
= PDR_PBB (pdr1
);
451 poly_bb_p pbb2
= PDR_PBB (pdr2
);
452 scop_p scop
= PBB_SCOP (pbb1
);
453 graphite_dim_t tdim1
= original_scattering_p
?
454 pbb_nb_scattering_orig (pbb1
) : pbb_nb_scattering_transform (pbb1
);
455 graphite_dim_t tdim2
= original_scattering_p
?
456 pbb_nb_scattering_orig (pbb2
) : pbb_nb_scattering_transform (pbb2
);
457 graphite_dim_t ddim1
= pbb_dim_iter_domain (pbb1
);
458 graphite_dim_t ddim2
= pbb_dim_iter_domain (pbb2
);
459 graphite_dim_t sdim1
= PDR_NB_SUBSCRIPTS (pdr1
) + 1;
460 graphite_dim_t sdim2
= PDR_NB_SUBSCRIPTS (pdr2
) + 1;
461 graphite_dim_t gdim
= scop_nb_params (scop
);
462 graphite_dim_t dim1
= pdr_dim (pdr1
);
463 graphite_dim_t dim2
= pdr_dim (pdr2
);
464 graphite_dim_t dim
= tdim1
+ tdim2
+ dim1
+ dim2
- gdim
;
465 ppl_Pointset_Powerset_C_Polyhedron_t res
;
466 ppl_Pointset_Powerset_C_Polyhedron_t idr1
, idr2
;
467 ppl_Pointset_Powerset_C_Polyhedron_t sc1
, sc2
, dreq
;
469 gcc_assert (PBB_SCOP (pbb1
) == PBB_SCOP (pbb2
));
471 combine_context_id_scat (&sc1
, pbb1
, original_scattering_p
);
472 combine_context_id_scat (&sc2
, pbb2
, original_scattering_p
);
474 ppl_insert_dimensions_pointset (sc1
, tdim1
+ ddim1
,
475 tdim2
+ ddim2
+ sdim1
+ sdim2
);
477 ppl_insert_dimensions_pointset (sc2
, 0, tdim1
+ ddim1
);
478 ppl_insert_dimensions_pointset (sc2
, tdim1
+ ddim1
+ tdim2
+ ddim2
,
481 idr1
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr1
), ddim1
, ddim1
+ gdim
,
482 tdim1
, tdim2
+ ddim2
);
483 idr2
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr2
), ddim2
, ddim2
+ gdim
,
484 tdim1
+ ddim1
+ tdim2
, sdim1
);
486 /* Now add the subscript equalities. */
487 dreq
= dr_equality_constraints (dim
, tdim1
+ ddim1
+ tdim2
+ ddim2
, sdim1
);
489 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res
, dim
, 0);
490 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, sc1
);
491 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, sc2
);
492 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr1
);
493 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr2
);
494 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, dreq
);
495 ppl_delete_Pointset_Powerset_C_Polyhedron (sc1
);
496 ppl_delete_Pointset_Powerset_C_Polyhedron (sc2
);
497 ppl_delete_Pointset_Powerset_C_Polyhedron (idr1
);
498 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2
);
499 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq
);
501 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res
))
503 ppl_Pointset_Powerset_C_Polyhedron_t lex
=
504 build_lexicographical_constraint (res
, dim
, MIN (tdim1
, tdim2
),
505 tdim1
+ ddim1
, direction
);
506 ppl_delete_Pointset_Powerset_C_Polyhedron (res
);
513 /* Build the dependence polyhedron for data references PDR1 and PDR2.
514 If possible use already cached information.
516 When DIRECTION is set to 1, compute the direct dependence from PDR1
517 to PDR2, and when DIRECTION is -1, compute the reversed dependence
518 relation, from PDR2 to PDR1. */
521 dependence_polyhedron (poly_dr_p pdr1
, poly_dr_p pdr2
,
522 int direction
, bool original_scattering_p
)
526 ppl_Pointset_Powerset_C_Polyhedron_t ddp
;
528 /* Return the PDDR from the cache if it already has been computed. */
529 if (original_scattering_p
)
532 scop_p scop
= PBB_SCOP (PDR_PBB (pdr1
));
536 x
= htab_find_slot (SCOP_ORIGINAL_PDDRS (scop
),
540 return (poly_ddr_p
) *x
;
543 if ((pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
544 || PDR_BASE_OBJECT_SET (pdr1
) != PDR_BASE_OBJECT_SET (pdr2
)
545 || PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
)
546 || !poly_drs_may_alias_p (pdr1
, pdr2
))
549 ddp
= dependence_polyhedron_1 (pdr1
, pdr2
, direction
,
550 original_scattering_p
);
552 res
= new_poly_ddr (pdr1
, pdr2
, ddp
, original_scattering_p
);
554 if (!(pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
555 && PDR_BASE_OBJECT_SET (pdr1
) != PDR_BASE_OBJECT_SET (pdr2
)
556 && poly_drs_may_alias_p (pdr1
, pdr2
))
557 PDDR_KIND (res
) = unknown_dependence
;
559 if (original_scattering_p
)
565 /* Return true when the data dependence relation between the data
566 references PDR1 belonging to PBB1 and PDR2 is part of a
570 reduction_dr_1 (poly_bb_p pbb1
, poly_dr_p pdr1
, poly_dr_p pdr2
)
575 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr
)
576 if (PDR_TYPE (pdr
) == PDR_WRITE
)
579 return same_pdr_p (pdr
, pdr1
) && same_pdr_p (pdr
, pdr2
);
582 /* Return true when the data dependence relation between the data
583 references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
584 part of a reduction. */
587 reduction_dr_p (poly_dr_p pdr1
, poly_dr_p pdr2
)
589 poly_bb_p pbb1
= PDR_PBB (pdr1
);
590 poly_bb_p pbb2
= PDR_PBB (pdr2
);
592 if (PBB_IS_REDUCTION (pbb1
))
593 return reduction_dr_1 (pbb1
, pdr1
, pdr2
);
595 if (PBB_IS_REDUCTION (pbb2
))
596 return reduction_dr_1 (pbb2
, pdr2
, pdr1
);
601 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
602 and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
606 graphite_legal_transform_dr (poly_dr_p pdr1
, poly_dr_p pdr2
)
608 ppl_Pointset_Powerset_C_Polyhedron_t po
, pt
;
609 graphite_dim_t ddim1
, otdim1
, otdim2
, ttdim1
, ttdim2
;
610 ppl_Pointset_Powerset_C_Polyhedron_t po_temp
;
611 ppl_dimension_type pdim
;
613 poly_ddr_p opddr
, tpddr
;
614 poly_bb_p pbb1
, pbb2
;
616 if (reduction_dr_p (pdr1
, pdr2
))
619 /* We build the reverse dependence relation for the transformed
620 scattering, such that when we intersect it with the original PO,
621 we get an empty intersection when the transform is legal:
622 i.e. the transform should reverse no dependences, and so PT, the
623 reversed transformed PDDR, should have no constraint from PO. */
624 opddr
= dependence_polyhedron (pdr1
, pdr2
, 1, true);
626 if (PDDR_KIND (opddr
) == unknown_dependence
)
629 /* There are no dependences between PDR1 and PDR2 in the original
630 version of the program, or after the transform, so the
631 transform is legal. */
632 if (pddr_is_empty (opddr
))
635 tpddr
= dependence_polyhedron (pdr1
, pdr2
, -1, false);
637 if (PDDR_KIND (tpddr
) == unknown_dependence
)
639 free_poly_ddr (tpddr
);
643 if (pddr_is_empty (tpddr
))
645 free_poly_ddr (tpddr
);
649 po
= PDDR_DDP (opddr
);
650 pt
= PDDR_DDP (tpddr
);
652 /* Copy PO into PO_TEMP, such that PO is not destroyed. PO is
653 stored in a cache and should not be modified or freed. */
654 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po
, &pdim
);
655 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&po_temp
,
657 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp
, po
);
659 /* Extend PO and PT to have the same dimensions. */
660 pbb1
= PDR_PBB (pdr1
);
661 pbb2
= PDR_PBB (pdr2
);
662 ddim1
= pbb_dim_iter_domain (pbb1
);
663 otdim1
= pbb_nb_scattering_orig (pbb1
);
664 otdim2
= pbb_nb_scattering_orig (pbb2
);
665 ttdim1
= pbb_nb_scattering_transform (pbb1
);
666 ttdim2
= pbb_nb_scattering_transform (pbb2
);
667 ppl_insert_dimensions_pointset (po_temp
, otdim1
, ttdim1
);
668 ppl_insert_dimensions_pointset (po_temp
, otdim1
+ ttdim1
+ ddim1
+ otdim2
,
670 ppl_insert_dimensions_pointset (pt
, 0, otdim1
);
671 ppl_insert_dimensions_pointset (pt
, otdim1
+ ttdim1
+ ddim1
, otdim2
);
673 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp
, pt
);
674 is_empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (po_temp
);
676 ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp
);
677 free_poly_ddr (tpddr
);
679 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
680 fprintf (dump_file
, "\nloop carries dependency.\n");
685 /* Return true when the data dependence relation for PBB1 and PBB2 is
686 part of a reduction. */
689 reduction_ddr_p (poly_bb_p pbb1
, poly_bb_p pbb2
)
691 return pbb1
== pbb2
&& PBB_IS_REDUCTION (pbb1
);
694 /* Iterates over the data references of PBB1 and PBB2 and detect
695 whether the transformed schedule is correct. */
698 graphite_legal_transform_bb (poly_bb_p pbb1
, poly_bb_p pbb2
)
701 poly_dr_p pdr1
, pdr2
;
703 if (!PBB_PDR_DUPLICATES_REMOVED (pbb1
))
704 pbb_remove_duplicate_pdrs (pbb1
);
706 if (!PBB_PDR_DUPLICATES_REMOVED (pbb2
))
707 pbb_remove_duplicate_pdrs (pbb2
);
709 if (reduction_ddr_p (pbb1
, pbb2
))
712 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
)
713 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
)
714 if (!graphite_legal_transform_dr (pdr1
, pdr2
))
720 /* Iterates over the SCOP and detect whether the transformed schedule
724 graphite_legal_transform (scop_p scop
)
727 poly_bb_p pbb1
, pbb2
;
729 timevar_push (TV_GRAPHITE_DATA_DEPS
);
731 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
732 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
733 if (!graphite_legal_transform_bb (pbb1
, pbb2
))
735 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
739 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
743 /* Returns TRUE when the dependence polyhedron between PDR1 and
744 PDR2 represents a loop carried dependence at level LEVEL. */
747 graphite_carried_dependence_level_k (poly_dr_p pdr1
, poly_dr_p pdr2
,
750 ppl_Pointset_Powerset_C_Polyhedron_t po
;
751 ppl_Pointset_Powerset_C_Polyhedron_t eqpp
;
752 graphite_dim_t tdim1
= pbb_nb_scattering_transform (PDR_PBB (pdr1
));
753 graphite_dim_t ddim1
= pbb_dim_iter_domain (PDR_PBB (pdr1
));
754 ppl_dimension_type dim
;
756 poly_ddr_p pddr
= dependence_polyhedron (pdr1
, pdr2
, 1, false);
758 if (PDDR_KIND (pddr
) == unknown_dependence
)
760 free_poly_ddr (pddr
);
764 if (pddr_is_empty (pddr
))
766 free_poly_ddr (pddr
);
770 po
= PDDR_DDP (pddr
);
771 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po
, &dim
);
772 eqpp
= build_pairwise_scheduling (dim
, level
, tdim1
+ ddim1
, 1);
774 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp
, po
);
775 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp
);
777 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp
);
778 free_poly_ddr (pddr
);
783 /* Check data dependency between PBB1 and PBB2 at level LEVEL. */
786 dependency_between_pbbs_p (poly_bb_p pbb1
, poly_bb_p pbb2
, int level
)
789 poly_dr_p pdr1
, pdr2
;
791 timevar_push (TV_GRAPHITE_DATA_DEPS
);
793 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
)
794 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
)
795 if (graphite_carried_dependence_level_k (pdr1
, pdr2
, level
))
797 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
801 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
805 /* Pretty print to FILE all the original data dependences of SCoP in
809 dot_original_deps_stmt_1 (FILE *file
, scop_p scop
)
812 poly_bb_p pbb1
, pbb2
;
813 poly_dr_p pdr1
, pdr2
;
815 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
816 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
818 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
)
819 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
)
820 if (!pddr_is_empty (dependence_polyhedron (pdr1
, pdr2
, 1, true)))
822 fprintf (file
, "OS%d -> OS%d\n",
823 pbb_index (pbb1
), pbb_index (pbb2
));
830 /* Pretty print to FILE all the transformed data dependences of SCoP in
834 dot_transformed_deps_stmt_1 (FILE *file
, scop_p scop
)
837 poly_bb_p pbb1
, pbb2
;
838 poly_dr_p pdr1
, pdr2
;
840 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
841 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
843 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
)
844 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
)
846 poly_ddr_p pddr
= dependence_polyhedron (pdr1
, pdr2
, 1, false);
848 if (!pddr_is_empty (pddr
))
850 fprintf (file
, "TS%d -> TS%d\n",
851 pbb_index (pbb1
), pbb_index (pbb2
));
853 free_poly_ddr (pddr
);
857 free_poly_ddr (pddr
);
864 /* Pretty print to FILE all the data dependences of SCoP in DOT
868 dot_deps_stmt_1 (FILE *file
, scop_p scop
)
870 fputs ("digraph all {\n", file
);
872 dot_original_deps_stmt_1 (file
, scop
);
873 dot_transformed_deps_stmt_1 (file
, scop
);
875 fputs ("}\n\n", file
);
878 /* Pretty print to FILE all the original data dependences of SCoP in
882 dot_original_deps (FILE *file
, scop_p scop
)
885 poly_bb_p pbb1
, pbb2
;
886 poly_dr_p pdr1
, pdr2
;
888 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
889 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
890 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
)
891 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
)
892 if (!pddr_is_empty (dependence_polyhedron (pdr1
, pdr2
, 1, true)))
893 fprintf (file
, "OS%d_D%d -> OS%d_D%d\n",
894 pbb_index (pbb1
), PDR_ID (pdr1
),
895 pbb_index (pbb2
), PDR_ID (pdr2
));
898 /* Pretty print to FILE all the transformed data dependences of SCoP in
902 dot_transformed_deps (FILE *file
, scop_p scop
)
905 poly_bb_p pbb1
, pbb2
;
906 poly_dr_p pdr1
, pdr2
;
908 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
)
909 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
)
910 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
)
911 FOR_EACH_VEC_ELT (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
)
913 poly_ddr_p pddr
= dependence_polyhedron (pdr1
, pdr2
, 1, false);
915 if (!pddr_is_empty (pddr
))
916 fprintf (file
, "TS%d_D%d -> TS%d_D%d\n",
917 pbb_index (pbb1
), PDR_ID (pdr1
),
918 pbb_index (pbb2
), PDR_ID (pdr2
));
920 free_poly_ddr (pddr
);
924 /* Pretty print to FILE all the data dependences of SCoP in DOT
928 dot_deps_1 (FILE *file
, scop_p scop
)
930 fputs ("digraph all {\n", file
);
932 dot_original_deps (file
, scop
);
933 dot_transformed_deps (file
, scop
);
935 fputs ("}\n\n", file
);
938 /* Display all the data dependences in SCoP using dotty. */
941 dot_deps (scop_p scop
)
943 /* When debugging, enable the following code. This cannot be used
944 in production compilers because it calls "system". */
946 FILE *stream
= fopen ("/tmp/scopdeps.dot", "w");
949 dot_deps_1 (stream
, scop
);
952 system ("dotty /tmp/scopdeps.dot &");
954 dot_deps_1 (stderr
, scop
);
958 /* Display all the statement dependences in SCoP using dotty. */
961 dot_deps_stmt (scop_p scop
)
963 /* When debugging, enable the following code. This cannot be used
964 in production compilers because it calls "system". */
966 FILE *stream
= fopen ("/tmp/scopdeps.dot", "w");
969 dot_deps_stmt_1 (stream
, scop
);
972 system ("dotty /tmp/scopdeps.dot &");
974 dot_deps_stmt_1 (stderr
, scop
);