1 /* Data dependence analysis for Graphite.
2 Copyright (C) 2009 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"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
36 #include "tree-chrec.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-data-ref.h"
39 #include "tree-pass.h"
41 #include "pointer-set.h"
45 #include "cloog/cloog.h"
48 #include "graphite-ppl.h"
50 #include "graphite-poly.h"
51 #include "graphite-dependences.h"
53 /* Returns a new polyhedral Data Dependence Relation (DDR). SOURCE is
54 the source data reference, SINK is the sink data reference. SOURCE
55 and SINK define an edge in the Data Dependence Graph (DDG). */
58 new_poly_ddr (poly_dr_p source
, poly_dr_p sink
,
59 ppl_Pointset_Powerset_C_Polyhedron_t ddp
)
63 pddr
= XNEW (struct poly_ddr
);
64 PDDR_SOURCE (pddr
) = source
;
65 PDDR_SINK (pddr
) = sink
;
66 PDDR_DDP (pddr
) = ddp
;
67 PDDR_KIND (pddr
) = unknown_dependence
;
72 /* Free the poly_ddr_p P. */
75 free_poly_ddr (void *p
)
77 poly_ddr_p pddr
= (poly_ddr_p
) p
;
78 ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr
));
82 /* Comparison function for poly_ddr hash table. */
85 eq_poly_ddr_p (const void *pddr1
, const void *pddr2
)
87 const struct poly_ddr
*p1
= (const struct poly_ddr
*) pddr1
;
88 const struct poly_ddr
*p2
= (const struct poly_ddr
*) pddr2
;
90 return (PDDR_SOURCE (p1
) == PDDR_SOURCE (p2
)
91 && PDDR_SINK (p1
) == PDDR_SINK (p2
));
94 /* Hash function for poly_ddr hashtable. */
97 hash_poly_ddr_p (const void *pddr
)
99 const struct poly_ddr
*p
= (const struct poly_ddr
*) pddr
;
101 return (hashval_t
) ((long) PDDR_SOURCE (p
) + (long) PDDR_SINK (p
));
104 /* Returns true when PDDR has no dependence. */
107 pddr_is_empty (poly_ddr_p pddr
)
109 if (PDDR_KIND (pddr
) != unknown_dependence
)
110 return PDDR_KIND (pddr
) == no_dependence
? true : false;
112 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PDDR_DDP (pddr
)))
114 PDDR_KIND (pddr
) = no_dependence
;
118 PDDR_KIND (pddr
) = has_dependence
;
122 /* Returns a polyhedron of dimension DIM.
124 Maps the dimensions [0, ..., cut - 1] of polyhedron P to OFFSET
125 and the dimensions [cut, ..., nb_dim] to DIM - GDIM. */
127 static ppl_Pointset_Powerset_C_Polyhedron_t
128 map_into_dep_poly (graphite_dim_t dim
, graphite_dim_t gdim
,
129 ppl_Pointset_Powerset_C_Polyhedron_t p
,
131 graphite_dim_t offset
)
133 ppl_Pointset_Powerset_C_Polyhedron_t res
;
135 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
137 ppl_insert_dimensions_pointset (res
, 0, offset
);
138 ppl_insert_dimensions_pointset (res
, offset
+ cut
,
139 dim
- offset
- cut
- gdim
);
144 /* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
145 transformed into "a CUT0 c CUT1' b"
147 Add NB0 zeros before "a": "00...0 a CUT0 c CUT1' b"
148 Add NB1 zeros between "a" and "c": "00...0 a 00...0 c CUT1' b"
149 Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b":
150 "00...0 a 00...0 c 00...0 b". */
152 static ppl_Pointset_Powerset_C_Polyhedron_t
153 map_dr_into_dep_poly (graphite_dim_t dim
,
154 ppl_Pointset_Powerset_C_Polyhedron_t dr
,
155 graphite_dim_t cut0
, graphite_dim_t cut1
,
156 graphite_dim_t nb0
, graphite_dim_t nb1
)
158 ppl_dimension_type pdim
;
159 ppl_dimension_type
*map
;
160 ppl_Pointset_Powerset_C_Polyhedron_t res
;
161 ppl_dimension_type i
;
163 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
165 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res
, &pdim
);
167 map
= (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, pdim
);
169 /* First mapping: move 'g' vector to right position. */
170 for (i
= 0; i
< cut0
; i
++)
173 for (i
= cut0
; i
< cut1
; i
++)
174 map
[i
] = pdim
- cut1
+ i
;
176 for (i
= cut1
; i
< pdim
; i
++)
177 map
[i
] = cut0
+ i
- cut1
;
179 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res
, map
, pdim
);
182 /* After swapping 's' and 'g' vectors, we have to update a new cut. */
183 cut1
= pdim
- cut1
+ cut0
;
185 ppl_insert_dimensions_pointset (res
, 0, nb0
);
186 ppl_insert_dimensions_pointset (res
, nb0
+ cut0
, nb1
);
187 ppl_insert_dimensions_pointset (res
, nb0
+ nb1
+ cut1
,
188 dim
- nb0
- nb1
- pdim
);
193 /* Builds a constraints of the form "POS1 - POS2 CSTR_TYPE C" */
195 static ppl_Constraint_t
196 build_pairwise_constraint (graphite_dim_t dim
,
197 graphite_dim_t pos1
, graphite_dim_t pos2
,
198 int c
, enum ppl_enum_Constraint_Type cstr_type
)
200 ppl_Linear_Expression_t expr
;
201 ppl_Constraint_t cstr
;
202 ppl_Coefficient_t coef
;
210 value_set_si (v_op
, -1);
211 value_set_si (v_c
, c
);
213 ppl_new_Coefficient (&coef
);
214 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
216 ppl_assign_Coefficient_from_mpz_t (coef
, v
);
217 ppl_Linear_Expression_add_to_coefficient (expr
, pos1
, coef
);
218 ppl_assign_Coefficient_from_mpz_t (coef
, v_op
);
219 ppl_Linear_Expression_add_to_coefficient (expr
, pos2
, coef
);
220 ppl_assign_Coefficient_from_mpz_t (coef
, v_c
);
221 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
223 ppl_new_Constraint (&cstr
, expr
, cstr_type
);
225 ppl_delete_Linear_Expression (expr
);
226 ppl_delete_Coefficient (coef
);
234 /* Builds subscript equality constraints. */
236 static ppl_Pointset_Powerset_C_Polyhedron_t
237 dr_equality_constraints (graphite_dim_t dim
,
238 graphite_dim_t pos
, graphite_dim_t nb_subscripts
)
240 ppl_Polyhedron_t subscript_equalities
;
241 ppl_Pointset_Powerset_C_Polyhedron_t res
;
248 value_set_si (v_op
, -1);
250 ppl_new_C_Polyhedron_from_space_dimension (&subscript_equalities
, dim
, 0);
251 for (i
= 0; i
< nb_subscripts
; i
++)
253 ppl_Linear_Expression_t expr
;
254 ppl_Constraint_t cstr
;
255 ppl_Coefficient_t coef
;
257 ppl_new_Coefficient (&coef
);
258 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
260 ppl_assign_Coefficient_from_mpz_t (coef
, v
);
261 ppl_Linear_Expression_add_to_coefficient (expr
, pos
+ i
, coef
);
262 ppl_assign_Coefficient_from_mpz_t (coef
, v_op
);
263 ppl_Linear_Expression_add_to_coefficient (expr
, pos
+ i
+ nb_subscripts
,
266 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
267 ppl_Polyhedron_add_constraint (subscript_equalities
, cstr
);
269 ppl_delete_Linear_Expression (expr
);
270 ppl_delete_Constraint (cstr
);
271 ppl_delete_Coefficient (coef
);
274 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
275 (&res
, subscript_equalities
);
278 ppl_delete_Polyhedron (subscript_equalities
);
283 /* Builds scheduling equality constraints. */
285 static ppl_Pointset_Powerset_C_Polyhedron_t
286 build_pairwise_scheduling_equality (graphite_dim_t dim
,
287 graphite_dim_t pos
, graphite_dim_t offset
)
289 ppl_Pointset_Powerset_C_Polyhedron_t res
;
290 ppl_Polyhedron_t equalities
;
291 ppl_Constraint_t cstr
;
293 ppl_new_C_Polyhedron_from_space_dimension (&equalities
, dim
, 0);
295 cstr
= build_pairwise_constraint (dim
, pos
, pos
+ offset
, 0,
296 PPL_CONSTRAINT_TYPE_EQUAL
);
297 ppl_Polyhedron_add_constraint (equalities
, cstr
);
298 ppl_delete_Constraint (cstr
);
300 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, equalities
);
301 ppl_delete_Polyhedron (equalities
);
305 /* Builds scheduling inequality constraints. */
307 static ppl_Pointset_Powerset_C_Polyhedron_t
308 build_pairwise_scheduling_inequality (graphite_dim_t dim
,
310 graphite_dim_t offset
,
313 ppl_Pointset_Powerset_C_Polyhedron_t res
;
314 ppl_Polyhedron_t equalities
;
315 ppl_Constraint_t cstr
;
317 ppl_new_C_Polyhedron_from_space_dimension (&equalities
, dim
, 0);
320 cstr
= build_pairwise_constraint (dim
, pos
, pos
+ offset
, -1,
321 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
323 cstr
= build_pairwise_constraint (dim
, pos
, pos
+ offset
, 1,
324 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
326 ppl_Polyhedron_add_constraint (equalities
, cstr
);
327 ppl_delete_Constraint (cstr
);
329 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, equalities
);
330 ppl_delete_Polyhedron (equalities
);
334 /* Returns true when adding the lexicographical constraints at level I
335 to the RES dependence polyhedron returns an empty polyhedron. */
338 lexicographically_gt_p (ppl_Pointset_Powerset_C_Polyhedron_t res
,
340 graphite_dim_t offset
,
341 bool direction
, graphite_dim_t i
)
343 ppl_Pointset_Powerset_C_Polyhedron_t ineq
;
346 ineq
= build_pairwise_scheduling_inequality (dim
, i
, offset
,
348 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (ineq
, res
);
349 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (ineq
);
351 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, ineq
);
352 ppl_delete_Pointset_Powerset_C_Polyhedron (ineq
);
357 /* Build the precedence constraints for the lexicographical comparison
358 of time vectors RES following the lexicographical order. */
361 build_lexicographically_gt_constraint (ppl_Pointset_Powerset_C_Polyhedron_t
*res
,
363 graphite_dim_t tdim1
,
364 graphite_dim_t offset
,
369 if (lexicographically_gt_p (*res
, dim
, offset
, direction
, 0))
372 for (i
= 0; i
< tdim1
- 1; i
++)
374 ppl_Pointset_Powerset_C_Polyhedron_t sceq
;
376 sceq
= build_pairwise_scheduling_equality (dim
, i
, offset
);
377 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res
, sceq
);
378 ppl_delete_Pointset_Powerset_C_Polyhedron (sceq
);
380 if (lexicographically_gt_p (*res
, dim
, offset
, direction
, i
+ 1))
386 ppl_delete_Pointset_Powerset_C_Polyhedron (*res
);
387 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (res
, dim
, 1);
391 /* Build the dependence polyhedron for data references PDR1 and PDR2.
392 The layout of the dependence polyhedron is:
397 | T1 and T2 the scattering dimensions for PDR1 and PDR2
398 | I1 and I2 the iteration domains
399 | S1 and S2 the subscripts
400 | G the global parameters. */
403 dependence_polyhedron_1 (poly_bb_p pbb1
, poly_bb_p pbb2
,
404 ppl_Pointset_Powerset_C_Polyhedron_t d1
,
405 ppl_Pointset_Powerset_C_Polyhedron_t d2
,
406 poly_dr_p pdr1
, poly_dr_p pdr2
,
407 ppl_Polyhedron_t s1
, ppl_Polyhedron_t s2
,
409 bool original_scattering_p
)
411 scop_p scop
= PBB_SCOP (pbb1
);
412 graphite_dim_t tdim1
= original_scattering_p
?
413 pbb_nb_scattering_orig (pbb1
) : pbb_nb_scattering_transform (pbb1
);
414 graphite_dim_t tdim2
= original_scattering_p
?
415 pbb_nb_scattering_orig (pbb2
) : pbb_nb_scattering_transform (pbb2
);
416 graphite_dim_t ddim1
= pbb_dim_iter_domain (pbb1
);
417 graphite_dim_t ddim2
= pbb_dim_iter_domain (pbb2
);
418 graphite_dim_t sdim1
= PDR_NB_SUBSCRIPTS (pdr1
) + 1;
419 graphite_dim_t gdim
= scop_nb_params (scop
);
420 graphite_dim_t dim1
= pdr_dim (pdr1
);
421 graphite_dim_t dim2
= pdr_dim (pdr2
);
422 graphite_dim_t dim
= tdim1
+ tdim2
+ dim1
+ dim2
- gdim
;
423 ppl_Pointset_Powerset_C_Polyhedron_t res
;
424 ppl_Pointset_Powerset_C_Polyhedron_t id1
, id2
, isc1
, isc2
, idr1
, idr2
;
425 ppl_Pointset_Powerset_C_Polyhedron_t sc1
, sc2
, dreq
;
426 ppl_Pointset_Powerset_C_Polyhedron_t context
;
428 gcc_assert (PBB_SCOP (pbb1
) == PBB_SCOP (pbb2
));
430 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
431 (&context
, SCOP_CONTEXT (scop
));
432 ppl_insert_dimensions_pointset (context
, 0, dim
- gdim
);
434 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc1
, s1
);
435 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc2
, s2
);
437 id1
= map_into_dep_poly (dim
, gdim
, d1
, ddim1
, tdim1
);
438 id2
= map_into_dep_poly (dim
, gdim
, d2
, ddim2
, tdim1
+ ddim1
+ tdim2
);
439 isc1
= map_into_dep_poly (dim
, gdim
, sc1
, ddim1
+ tdim1
, 0);
440 isc2
= map_into_dep_poly (dim
, gdim
, sc2
, ddim2
+ tdim2
, tdim1
+ ddim1
);
442 idr1
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr1
), ddim1
, ddim1
+ gdim
,
443 tdim1
, tdim2
+ ddim2
);
444 idr2
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr2
), ddim2
, ddim2
+ gdim
,
445 tdim1
+ ddim1
+ tdim2
, sdim1
);
447 /* Now add the subscript equalities. */
448 dreq
= dr_equality_constraints (dim
, tdim1
+ ddim1
+ tdim2
+ ddim2
, sdim1
);
450 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res
, dim
, 0);
451 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, context
);
452 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, id1
);
453 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, id2
);
454 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, isc1
);
455 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, isc2
);
456 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr1
);
457 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr2
);
458 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, dreq
);
459 ppl_delete_Pointset_Powerset_C_Polyhedron (context
);
460 ppl_delete_Pointset_Powerset_C_Polyhedron (id1
);
461 ppl_delete_Pointset_Powerset_C_Polyhedron (id2
);
462 ppl_delete_Pointset_Powerset_C_Polyhedron (sc1
);
463 ppl_delete_Pointset_Powerset_C_Polyhedron (sc2
);
464 ppl_delete_Pointset_Powerset_C_Polyhedron (isc1
);
465 ppl_delete_Pointset_Powerset_C_Polyhedron (isc2
);
466 ppl_delete_Pointset_Powerset_C_Polyhedron (idr1
);
467 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2
);
468 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq
);
470 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res
))
471 build_lexicographically_gt_constraint (&res
, dim
, MIN (tdim1
, tdim2
),
472 tdim1
+ ddim1
, direction
);
474 return new_poly_ddr (pdr1
, pdr2
, res
);
477 /* Build the dependence polyhedron for data references PDR1 and PDR2.
478 If possible use already cached information. */
481 dependence_polyhedron (poly_bb_p pbb1
, poly_bb_p pbb2
,
482 ppl_Pointset_Powerset_C_Polyhedron_t d1
,
483 ppl_Pointset_Powerset_C_Polyhedron_t d2
,
484 poly_dr_p pdr1
, poly_dr_p pdr2
,
485 ppl_Polyhedron_t s1
, ppl_Polyhedron_t s2
,
487 bool original_scattering_p
)
492 if (original_scattering_p
)
498 x
= htab_find_slot (SCOP_ORIGINAL_PDDRS (PBB_SCOP (pbb1
)),
502 return (poly_ddr_p
) *x
;
505 res
= dependence_polyhedron_1 (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
,
506 s1
, s2
, direction
, original_scattering_p
);
508 if (original_scattering_p
)
514 /* Returns the PDDR corresponding to the original schedule, or NULL if
515 the dependence relation is empty or unknown (cannot judge dependency
516 under polyhedral model). */
519 pddr_original_scattering (poly_bb_p pbb1
, poly_bb_p pbb2
,
520 poly_dr_p pdr1
, poly_dr_p pdr2
)
523 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
524 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
525 ppl_Polyhedron_t so1
= PBB_ORIGINAL_SCATTERING (pbb1
);
526 ppl_Polyhedron_t so2
= PBB_ORIGINAL_SCATTERING (pbb2
);
528 if ((pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
529 || PDR_BASE_OBJECT_SET (pdr1
) != PDR_BASE_OBJECT_SET (pdr2
)
530 || PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
))
533 pddr
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, so1
, so2
,
535 if (pddr_is_empty (pddr
))
541 /* Returns the PDDR corresponding to the transformed schedule, or NULL if
542 the dependence relation is empty or unknown (cannot judge dependency
543 under polyhedral model). */
546 pddr_transformed_scattering (poly_bb_p pbb1
, poly_bb_p pbb2
,
547 poly_dr_p pdr1
, poly_dr_p pdr2
)
550 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
551 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
552 ppl_Polyhedron_t st1
= PBB_ORIGINAL_SCATTERING (pbb1
);
553 ppl_Polyhedron_t st2
= PBB_ORIGINAL_SCATTERING (pbb2
);
555 if ((pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
556 || PDR_BASE_OBJECT_SET (pdr1
) != PDR_BASE_OBJECT_SET (pdr2
)
557 || PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
))
560 pddr
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, st1
, st2
,
562 if (pddr_is_empty (pddr
))
569 /* Return true when the data dependence relation between the data
570 references PDR1 belonging to PBB1 and PDR2 is part of a
574 reduction_dr_1 (poly_bb_p pbb1
, poly_dr_p pdr1
, poly_dr_p pdr2
)
579 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr
); i
++)
580 if (PDR_TYPE (pdr
) == PDR_WRITE
)
583 return same_pdr_p (pdr
, pdr1
) && same_pdr_p (pdr
, pdr2
);
586 /* Return true when the data dependence relation between the data
587 references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
588 part of a reduction. */
591 reduction_dr_p (poly_bb_p pbb1
, poly_bb_p pbb2
,
592 poly_dr_p pdr1
, poly_dr_p pdr2
)
594 if (PBB_IS_REDUCTION (pbb1
))
595 return reduction_dr_1 (pbb1
, pdr1
, pdr2
);
597 if (PBB_IS_REDUCTION (pbb2
))
598 return reduction_dr_1 (pbb2
, pdr2
, pdr1
);
603 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
604 and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
608 graphite_legal_transform_dr (poly_bb_p pbb1
, poly_bb_p pbb2
,
609 poly_dr_p pdr1
, poly_dr_p pdr2
)
611 ppl_Polyhedron_t st1
, st2
;
612 ppl_Pointset_Powerset_C_Polyhedron_t po
, pt
;
613 graphite_dim_t ddim1
, otdim1
, otdim2
, ttdim1
, ttdim2
;
614 ppl_Pointset_Powerset_C_Polyhedron_t temp
;
615 ppl_dimension_type pdim
;
618 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
619 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
621 if (reduction_dr_p (pbb1
, pbb2
, pdr1
, pdr2
))
624 pddr
= pddr_original_scattering (pbb1
, pbb2
, pdr1
, pdr2
);
628 po
= PDDR_DDP (pddr
);
630 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
631 fprintf (dump_file
, "\nloop carries dependency.\n");
633 st1
= PBB_TRANSFORMED_SCATTERING (pbb1
);
634 st2
= PBB_TRANSFORMED_SCATTERING (pbb2
);
635 ddim1
= pbb_dim_iter_domain (pbb1
);
636 otdim1
= pbb_nb_scattering_orig (pbb1
);
637 otdim2
= pbb_nb_scattering_orig (pbb2
);
638 ttdim1
= pbb_nb_scattering_transform (pbb1
);
639 ttdim2
= pbb_nb_scattering_transform (pbb2
);
641 /* Copy the PO polyhedron into the TEMP, so it is not destroyed.
642 Keep in mind, that PO polyhedron might be restored from the cache
643 and should not be modified! */
644 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po
, &pdim
);
645 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&temp
, pdim
, 0);
646 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp
, po
);
648 pddr
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, st1
, st2
,
650 pt
= PDDR_DDP (pddr
);
652 /* Extend PO and PT to have the same dimensions. */
653 ppl_insert_dimensions_pointset (temp
, otdim1
, ttdim1
);
654 ppl_insert_dimensions_pointset (temp
, otdim1
+ ttdim1
+ ddim1
+ otdim2
, ttdim2
);
655 ppl_insert_dimensions_pointset (pt
, 0, otdim1
);
656 ppl_insert_dimensions_pointset (pt
, otdim1
+ ttdim1
+ ddim1
, otdim2
);
658 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp
, pt
);
659 is_empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp
);
661 ppl_delete_Pointset_Powerset_C_Polyhedron (temp
);
662 free_poly_ddr (pddr
);
667 /* Return true when the data dependence relation for PBB1 and PBB2 is
668 part of a reduction. */
671 reduction_ddr_p (poly_bb_p pbb1
, poly_bb_p pbb2
)
673 return pbb1
== pbb2
&& PBB_IS_REDUCTION (pbb1
);
676 /* Iterates over the data references of PBB1 and PBB2 and detect
677 whether the transformed schedule is correct. */
680 graphite_legal_transform_bb (poly_bb_p pbb1
, poly_bb_p pbb2
)
683 poly_dr_p pdr1
, pdr2
;
685 if (!PBB_PDR_DUPLICATES_REMOVED (pbb1
))
686 pbb_remove_duplicate_pdrs (pbb1
);
688 if (!PBB_PDR_DUPLICATES_REMOVED (pbb2
))
689 pbb_remove_duplicate_pdrs (pbb2
);
691 if (reduction_ddr_p (pbb1
, pbb2
))
694 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
); i
++)
695 for (j
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
); j
++)
696 if (!graphite_legal_transform_dr (pbb1
, pbb2
, pdr1
, pdr2
))
702 /* Iterates over the SCOP and detect whether the transformed schedule
706 graphite_legal_transform (scop_p scop
)
709 poly_bb_p pbb1
, pbb2
;
711 timevar_push (TV_GRAPHITE_DATA_DEPS
);
713 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
714 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
715 if (!graphite_legal_transform_bb (pbb1
, pbb2
))
717 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
721 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
725 /* Remove all the dimensions except alias information at dimension
729 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset
,
730 ppl_dimension_type alias_dim
)
732 ppl_dimension_type
*ds
;
733 ppl_dimension_type access_dim
;
736 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset
,
738 ds
= XNEWVEC (ppl_dimension_type
, access_dim
-1);
739 for (i
= 0; i
< access_dim
; i
++)
748 ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset
,
754 /* Return true when PDR1 and PDR2 may alias. */
757 poly_drs_may_alias_p (poly_dr_p pdr1
, poly_dr_p pdr2
)
759 ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1
, alias_powerset2
;
760 ppl_Pointset_Powerset_C_Polyhedron_t accesses1
= PDR_ACCESSES (pdr1
);
761 ppl_Pointset_Powerset_C_Polyhedron_t accesses2
= PDR_ACCESSES (pdr2
);
762 ppl_dimension_type alias_dim1
= pdr_alias_set_dim (pdr1
);
763 ppl_dimension_type alias_dim2
= pdr_alias_set_dim (pdr2
);
766 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
767 (&alias_powerset1
, accesses1
);
768 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
769 (&alias_powerset2
, accesses2
);
771 build_alias_set_powerset (alias_powerset1
, alias_dim1
);
772 build_alias_set_powerset (alias_powerset2
, alias_dim2
);
774 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
775 (alias_powerset1
, alias_powerset2
);
777 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1
);
779 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1
);
780 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2
);
785 /* Returns TRUE when the dependence polyhedron between PDR1 and
786 PDR2 represents a loop carried dependence at level LEVEL. */
789 graphite_carried_dependence_level_k (poly_dr_p pdr1
, poly_dr_p pdr2
,
792 poly_bb_p pbb1
= PDR_PBB (pdr1
);
793 poly_bb_p pbb2
= PDR_PBB (pdr2
);
794 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
795 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
796 ppl_Polyhedron_t so1
= PBB_TRANSFORMED_SCATTERING (pbb1
);
797 ppl_Polyhedron_t so2
= PBB_TRANSFORMED_SCATTERING (pbb2
);
798 ppl_Pointset_Powerset_C_Polyhedron_t po
;
799 ppl_Pointset_Powerset_C_Polyhedron_t eqpp
;
800 graphite_dim_t tdim1
= pbb_nb_scattering_transform (pbb1
);
801 graphite_dim_t ddim1
= pbb_dim_iter_domain (pbb1
);
802 ppl_dimension_type dim
;
805 int obj_base_set1
= PDR_BASE_OBJECT_SET (pdr1
);
806 int obj_base_set2
= PDR_BASE_OBJECT_SET (pdr2
);
808 if ((pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
809 || !poly_drs_may_alias_p (pdr1
, pdr2
))
812 if (obj_base_set1
!= obj_base_set2
)
815 if (PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
))
818 pddr
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, so1
, so2
,
821 if (pddr_is_empty (pddr
))
824 po
= PDDR_DDP (pddr
);
825 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po
, &dim
);
826 eqpp
= build_pairwise_scheduling_inequality (dim
, level
, tdim1
+ ddim1
, 1);
828 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp
, po
);
829 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp
);
831 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp
);
835 /* Check data dependency between PBB1 and PBB2 at level LEVEL. */
838 dependency_between_pbbs_p (poly_bb_p pbb1
, poly_bb_p pbb2
, int level
)
841 poly_dr_p pdr1
, pdr2
;
843 timevar_push (TV_GRAPHITE_DATA_DEPS
);
845 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
); i
++)
846 for (j
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
); j
++)
847 if (graphite_carried_dependence_level_k (pdr1
, pdr2
, level
))
849 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
853 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
857 /* Pretty print to FILE all the original data dependences of SCoP in
861 dot_original_deps_stmt_1 (FILE *file
, scop_p scop
)
864 poly_bb_p pbb1
, pbb2
;
865 poly_dr_p pdr1
, pdr2
;
867 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
868 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
870 for (k
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
); k
++)
871 for (l
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
); l
++)
872 if (pddr_original_scattering (pbb1
, pbb2
, pdr1
, pdr2
))
874 fprintf (file
, "OS%d -> OS%d\n",
875 pbb_index (pbb1
), pbb_index (pbb2
));
882 /* Pretty print to FILE all the transformed data dependences of SCoP in
886 dot_transformed_deps_stmt_1 (FILE *file
, scop_p scop
)
889 poly_bb_p pbb1
, pbb2
;
890 poly_dr_p pdr1
, pdr2
;
892 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
893 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
895 for (k
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
); k
++)
896 for (l
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
); l
++)
897 if (pddr_transformed_scattering (pbb1
, pbb2
, pdr1
, pdr2
))
899 fprintf (file
, "TS%d -> TS%d\n",
900 pbb_index (pbb1
), pbb_index (pbb2
));
908 /* Pretty print to FILE all the data dependences of SCoP in DOT
912 dot_deps_stmt_1 (FILE *file
, scop_p scop
)
914 fputs ("digraph all {\n", file
);
916 dot_original_deps_stmt_1 (file
, scop
);
917 dot_transformed_deps_stmt_1 (file
, scop
);
919 fputs ("}\n\n", file
);
922 /* Pretty print to FILE all the original data dependences of SCoP in
926 dot_original_deps (FILE *file
, scop_p scop
)
929 poly_bb_p pbb1
, pbb2
;
930 poly_dr_p pdr1
, pdr2
;
932 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
933 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
934 for (k
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
); k
++)
935 for (l
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
); l
++)
936 if (pddr_original_scattering (pbb1
, pbb2
, pdr1
, pdr2
))
937 fprintf (file
, "OS%d_D%d -> OS%d_D%d\n",
938 pbb_index (pbb1
), PDR_ID (pdr1
),
939 pbb_index (pbb2
), PDR_ID (pdr2
));
942 /* Pretty print to FILE all the transformed data dependences of SCoP in
946 dot_transformed_deps (FILE *file
, scop_p scop
)
949 poly_bb_p pbb1
, pbb2
;
950 poly_dr_p pdr1
, pdr2
;
952 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
953 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
954 for (k
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
); k
++)
955 for (l
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
); l
++)
956 if (pddr_transformed_scattering (pbb1
, pbb2
, pdr1
, pdr2
))
957 fprintf (file
, "TS%d_D%d -> TS%d_D%d\n",
958 pbb_index (pbb1
), PDR_ID (pdr1
),
959 pbb_index (pbb2
), PDR_ID (pdr2
));
962 /* Pretty print to FILE all the data dependences of SCoP in DOT
966 dot_deps_1 (FILE *file
, scop_p scop
)
968 fputs ("digraph all {\n", file
);
970 dot_original_deps (file
, scop
);
971 dot_transformed_deps (file
, scop
);
973 fputs ("}\n\n", file
);
976 /* Display all the data dependences in SCoP using dotty. */
979 dot_deps (scop_p scop
)
981 /* When debugging, enable the following code. This cannot be used
982 in production compilers because it calls "system". */
985 FILE *stream
= fopen ("/tmp/scopdeps.dot", "w");
988 dot_deps_1 (stream
, scop
);
991 x
= system ("dotty /tmp/scopdeps.dot");
993 dot_deps_1 (stderr
, scop
);
997 /* Display all the statement dependences in SCoP using dotty. */
1000 dot_deps_stmt (scop_p scop
)
1002 /* When debugging, enable the following code. This cannot be used
1003 in production compilers because it calls "system". */
1006 FILE *stream
= fopen ("/tmp/scopdeps.dot", "w");
1007 gcc_assert (stream
);
1009 dot_deps_stmt_1 (stream
, scop
);
1012 x
= system ("dotty /tmp/scopdeps.dot");
1014 dot_deps_1 (stderr
, scop
);