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-data-ref.h"
38 #include "tree-scalar-evolution.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 subscript equality constraints. */
195 static ppl_Pointset_Powerset_C_Polyhedron_t
196 dr_equality_constraints (graphite_dim_t dim
,
197 graphite_dim_t pos
, graphite_dim_t nb_subscripts
)
199 ppl_Polyhedron_t eqs
;
200 ppl_Pointset_Powerset_C_Polyhedron_t res
;
203 ppl_new_C_Polyhedron_from_space_dimension (&eqs
, dim
, 0);
205 for (i
= 0; i
< nb_subscripts
; i
++)
207 ppl_Constraint_t cstr
208 = ppl_build_relation (dim
, pos
+ i
, pos
+ i
+ nb_subscripts
,
209 0, PPL_CONSTRAINT_TYPE_EQUAL
);
210 ppl_Polyhedron_add_constraint (eqs
, cstr
);
211 ppl_delete_Constraint (cstr
);
214 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, eqs
);
215 ppl_delete_Polyhedron (eqs
);
219 /* Builds scheduling equality constraints. */
221 static ppl_Pointset_Powerset_C_Polyhedron_t
222 build_pairwise_scheduling_equality (graphite_dim_t dim
,
223 graphite_dim_t pos
, graphite_dim_t offset
)
225 ppl_Pointset_Powerset_C_Polyhedron_t res
;
226 ppl_Polyhedron_t equalities
;
227 ppl_Constraint_t cstr
;
229 ppl_new_C_Polyhedron_from_space_dimension (&equalities
, dim
, 0);
231 cstr
= ppl_build_relation (dim
, pos
, pos
+ offset
, 0,
232 PPL_CONSTRAINT_TYPE_EQUAL
);
233 ppl_Polyhedron_add_constraint (equalities
, cstr
);
234 ppl_delete_Constraint (cstr
);
236 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, equalities
);
237 ppl_delete_Polyhedron (equalities
);
241 /* Builds scheduling inequality constraints. */
243 static ppl_Pointset_Powerset_C_Polyhedron_t
244 build_pairwise_scheduling_inequality (graphite_dim_t dim
,
246 graphite_dim_t offset
,
249 ppl_Pointset_Powerset_C_Polyhedron_t res
;
250 ppl_Polyhedron_t equalities
;
251 ppl_Constraint_t cstr
;
253 ppl_new_C_Polyhedron_from_space_dimension (&equalities
, dim
, 0);
256 cstr
= ppl_build_relation (dim
, pos
, pos
+ offset
, -1,
257 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
259 cstr
= ppl_build_relation (dim
, pos
, pos
+ offset
, 1,
260 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
262 ppl_Polyhedron_add_constraint (equalities
, cstr
);
263 ppl_delete_Constraint (cstr
);
265 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, equalities
);
266 ppl_delete_Polyhedron (equalities
);
270 /* Returns true when adding the lexicographical constraints at level I
271 to the RES dependence polyhedron returns an empty polyhedron. */
274 lexicographically_gt_p (ppl_Pointset_Powerset_C_Polyhedron_t res
,
276 graphite_dim_t offset
,
277 bool direction
, graphite_dim_t i
)
279 ppl_Pointset_Powerset_C_Polyhedron_t ineq
;
282 ineq
= build_pairwise_scheduling_inequality (dim
, i
, offset
,
284 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (ineq
, res
);
285 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (ineq
);
287 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, ineq
);
288 ppl_delete_Pointset_Powerset_C_Polyhedron (ineq
);
293 /* Build the precedence constraints for the lexicographical comparison
294 of time vectors RES following the lexicographical order. */
297 build_lexicographically_gt_constraint (ppl_Pointset_Powerset_C_Polyhedron_t
*res
,
299 graphite_dim_t tdim1
,
300 graphite_dim_t offset
,
305 if (lexicographically_gt_p (*res
, dim
, offset
, direction
, 0))
308 for (i
= 0; i
< tdim1
- 1; i
++)
310 ppl_Pointset_Powerset_C_Polyhedron_t sceq
;
312 sceq
= build_pairwise_scheduling_equality (dim
, i
, offset
);
313 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res
, sceq
);
314 ppl_delete_Pointset_Powerset_C_Polyhedron (sceq
);
316 if (lexicographically_gt_p (*res
, dim
, offset
, direction
, i
+ 1))
322 ppl_delete_Pointset_Powerset_C_Polyhedron (*res
);
323 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (res
, dim
, 1);
327 /* Build the dependence polyhedron for data references PDR1 and PDR2.
328 The layout of the dependence polyhedron is:
333 | T1 and T2 the scattering dimensions for PDR1 and PDR2
334 | I1 and I2 the iteration domains
335 | S1 and S2 the subscripts
336 | G the global parameters. */
339 dependence_polyhedron_1 (poly_bb_p pbb1
, poly_bb_p pbb2
,
340 ppl_Pointset_Powerset_C_Polyhedron_t d1
,
341 ppl_Pointset_Powerset_C_Polyhedron_t d2
,
342 poly_dr_p pdr1
, poly_dr_p pdr2
,
343 ppl_Polyhedron_t s1
, ppl_Polyhedron_t s2
,
345 bool original_scattering_p
)
347 scop_p scop
= PBB_SCOP (pbb1
);
348 graphite_dim_t tdim1
= original_scattering_p
?
349 pbb_nb_scattering_orig (pbb1
) : pbb_nb_scattering_transform (pbb1
);
350 graphite_dim_t tdim2
= original_scattering_p
?
351 pbb_nb_scattering_orig (pbb2
) : pbb_nb_scattering_transform (pbb2
);
352 graphite_dim_t ddim1
= pbb_dim_iter_domain (pbb1
);
353 graphite_dim_t ddim2
= pbb_dim_iter_domain (pbb2
);
354 graphite_dim_t sdim1
= PDR_NB_SUBSCRIPTS (pdr1
) + 1;
355 graphite_dim_t gdim
= scop_nb_params (scop
);
356 graphite_dim_t dim1
= pdr_dim (pdr1
);
357 graphite_dim_t dim2
= pdr_dim (pdr2
);
358 graphite_dim_t dim
= tdim1
+ tdim2
+ dim1
+ dim2
- gdim
;
359 ppl_Pointset_Powerset_C_Polyhedron_t res
;
360 ppl_Pointset_Powerset_C_Polyhedron_t id1
, id2
, isc1
, isc2
, idr1
, idr2
;
361 ppl_Pointset_Powerset_C_Polyhedron_t sc1
, sc2
, dreq
;
362 ppl_Pointset_Powerset_C_Polyhedron_t context
;
364 gcc_assert (PBB_SCOP (pbb1
) == PBB_SCOP (pbb2
));
366 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
367 (&context
, SCOP_CONTEXT (scop
));
368 ppl_insert_dimensions_pointset (context
, 0, dim
- gdim
);
370 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc1
, s1
);
371 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc2
, s2
);
373 id1
= map_into_dep_poly (dim
, gdim
, d1
, ddim1
, tdim1
);
374 id2
= map_into_dep_poly (dim
, gdim
, d2
, ddim2
, tdim1
+ ddim1
+ tdim2
);
375 isc1
= map_into_dep_poly (dim
, gdim
, sc1
, ddim1
+ tdim1
, 0);
376 isc2
= map_into_dep_poly (dim
, gdim
, sc2
, ddim2
+ tdim2
, tdim1
+ ddim1
);
378 idr1
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr1
), ddim1
, ddim1
+ gdim
,
379 tdim1
, tdim2
+ ddim2
);
380 idr2
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr2
), ddim2
, ddim2
+ gdim
,
381 tdim1
+ ddim1
+ tdim2
, sdim1
);
383 /* Now add the subscript equalities. */
384 dreq
= dr_equality_constraints (dim
, tdim1
+ ddim1
+ tdim2
+ ddim2
, sdim1
);
386 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res
, dim
, 0);
387 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, context
);
388 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, id1
);
389 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, id2
);
390 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, isc1
);
391 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, isc2
);
392 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr1
);
393 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr2
);
394 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, dreq
);
395 ppl_delete_Pointset_Powerset_C_Polyhedron (context
);
396 ppl_delete_Pointset_Powerset_C_Polyhedron (id1
);
397 ppl_delete_Pointset_Powerset_C_Polyhedron (id2
);
398 ppl_delete_Pointset_Powerset_C_Polyhedron (sc1
);
399 ppl_delete_Pointset_Powerset_C_Polyhedron (sc2
);
400 ppl_delete_Pointset_Powerset_C_Polyhedron (isc1
);
401 ppl_delete_Pointset_Powerset_C_Polyhedron (isc2
);
402 ppl_delete_Pointset_Powerset_C_Polyhedron (idr1
);
403 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2
);
404 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq
);
406 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res
))
407 build_lexicographically_gt_constraint (&res
, dim
, MIN (tdim1
, tdim2
),
408 tdim1
+ ddim1
, direction
);
410 return new_poly_ddr (pdr1
, pdr2
, res
);
413 /* Build the dependence polyhedron for data references PDR1 and PDR2.
414 If possible use already cached information. */
417 dependence_polyhedron (poly_bb_p pbb1
, poly_bb_p pbb2
,
418 ppl_Pointset_Powerset_C_Polyhedron_t d1
,
419 ppl_Pointset_Powerset_C_Polyhedron_t d2
,
420 poly_dr_p pdr1
, poly_dr_p pdr2
,
421 ppl_Polyhedron_t s1
, ppl_Polyhedron_t s2
,
423 bool original_scattering_p
)
428 if (original_scattering_p
)
434 x
= htab_find_slot (SCOP_ORIGINAL_PDDRS (PBB_SCOP (pbb1
)),
438 return (poly_ddr_p
) *x
;
441 res
= dependence_polyhedron_1 (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
,
442 s1
, s2
, direction
, original_scattering_p
);
444 if (original_scattering_p
)
451 poly_drs_may_alias_p (poly_dr_p pdr1
, poly_dr_p pdr2
);
453 /* Returns the PDDR corresponding to the original schedule, or NULL if
454 the dependence relation is empty or unknown (cannot judge dependency
455 under polyhedral model). */
458 pddr_original_scattering (poly_bb_p pbb1
, poly_bb_p pbb2
,
459 poly_dr_p pdr1
, poly_dr_p pdr2
)
462 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
463 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
464 ppl_Polyhedron_t so1
= PBB_ORIGINAL_SCATTERING (pbb1
);
465 ppl_Polyhedron_t so2
= PBB_ORIGINAL_SCATTERING (pbb2
);
467 if ((pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
468 || PDR_BASE_OBJECT_SET (pdr1
) != PDR_BASE_OBJECT_SET (pdr2
)
469 || PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
))
472 pddr
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, so1
, so2
,
474 if (pddr_is_empty (pddr
))
480 /* Returns the PDDR corresponding to the transformed schedule, or NULL if
481 the dependence relation is empty or unknown (cannot judge dependency
482 under polyhedral model). */
485 pddr_transformed_scattering (poly_bb_p pbb1
, poly_bb_p pbb2
,
486 poly_dr_p pdr1
, poly_dr_p pdr2
)
489 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
490 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
491 ppl_Polyhedron_t st1
= PBB_ORIGINAL_SCATTERING (pbb1
);
492 ppl_Polyhedron_t st2
= PBB_ORIGINAL_SCATTERING (pbb2
);
494 if ((pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
495 || PDR_BASE_OBJECT_SET (pdr1
) != PDR_BASE_OBJECT_SET (pdr2
)
496 || PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
))
499 pddr
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, st1
, st2
,
501 if (pddr_is_empty (pddr
))
508 /* Return true when the data dependence relation between the data
509 references PDR1 belonging to PBB1 and PDR2 is part of a
513 reduction_dr_1 (poly_bb_p pbb1
, poly_dr_p pdr1
, poly_dr_p pdr2
)
518 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr
); i
++)
519 if (PDR_TYPE (pdr
) == PDR_WRITE
)
522 return same_pdr_p (pdr
, pdr1
) && same_pdr_p (pdr
, pdr2
);
525 /* Return true when the data dependence relation between the data
526 references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
527 part of a reduction. */
530 reduction_dr_p (poly_bb_p pbb1
, poly_bb_p pbb2
,
531 poly_dr_p pdr1
, poly_dr_p pdr2
)
533 if (PBB_IS_REDUCTION (pbb1
))
534 return reduction_dr_1 (pbb1
, pdr1
, pdr2
);
536 if (PBB_IS_REDUCTION (pbb2
))
537 return reduction_dr_1 (pbb2
, pdr2
, pdr1
);
542 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
543 and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
547 graphite_legal_transform_dr (poly_bb_p pbb1
, poly_bb_p pbb2
,
548 poly_dr_p pdr1
, poly_dr_p pdr2
)
550 ppl_Polyhedron_t st1
, st2
;
551 ppl_Pointset_Powerset_C_Polyhedron_t po
, pt
;
552 graphite_dim_t ddim1
, otdim1
, otdim2
, ttdim1
, ttdim2
;
553 ppl_Pointset_Powerset_C_Polyhedron_t temp
;
554 ppl_dimension_type pdim
;
557 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
558 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
560 if (reduction_dr_p (pbb1
, pbb2
, pdr1
, pdr2
))
563 pddr
= pddr_original_scattering (pbb1
, pbb2
, pdr1
, pdr2
);
567 po
= PDDR_DDP (pddr
);
569 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
570 fprintf (dump_file
, "\nloop carries dependency.\n");
572 st1
= PBB_TRANSFORMED_SCATTERING (pbb1
);
573 st2
= PBB_TRANSFORMED_SCATTERING (pbb2
);
574 ddim1
= pbb_dim_iter_domain (pbb1
);
575 otdim1
= pbb_nb_scattering_orig (pbb1
);
576 otdim2
= pbb_nb_scattering_orig (pbb2
);
577 ttdim1
= pbb_nb_scattering_transform (pbb1
);
578 ttdim2
= pbb_nb_scattering_transform (pbb2
);
580 /* Copy the PO polyhedron into the TEMP, so it is not destroyed.
581 Keep in mind, that PO polyhedron might be restored from the cache
582 and should not be modified! */
583 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po
, &pdim
);
584 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&temp
, pdim
, 0);
585 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp
, po
);
587 pddr
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, st1
, st2
,
589 pt
= PDDR_DDP (pddr
);
591 /* Extend PO and PT to have the same dimensions. */
592 ppl_insert_dimensions_pointset (temp
, otdim1
, ttdim1
);
593 ppl_insert_dimensions_pointset (temp
, otdim1
+ ttdim1
+ ddim1
+ otdim2
, ttdim2
);
594 ppl_insert_dimensions_pointset (pt
, 0, otdim1
);
595 ppl_insert_dimensions_pointset (pt
, otdim1
+ ttdim1
+ ddim1
, otdim2
);
597 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp
, pt
);
598 is_empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp
);
600 ppl_delete_Pointset_Powerset_C_Polyhedron (temp
);
601 free_poly_ddr (pddr
);
606 /* Return true when the data dependence relation for PBB1 and PBB2 is
607 part of a reduction. */
610 reduction_ddr_p (poly_bb_p pbb1
, poly_bb_p pbb2
)
612 return pbb1
== pbb2
&& PBB_IS_REDUCTION (pbb1
);
615 /* Iterates over the data references of PBB1 and PBB2 and detect
616 whether the transformed schedule is correct. */
619 graphite_legal_transform_bb (poly_bb_p pbb1
, poly_bb_p pbb2
)
622 poly_dr_p pdr1
, pdr2
;
624 if (!PBB_PDR_DUPLICATES_REMOVED (pbb1
))
625 pbb_remove_duplicate_pdrs (pbb1
);
627 if (!PBB_PDR_DUPLICATES_REMOVED (pbb2
))
628 pbb_remove_duplicate_pdrs (pbb2
);
630 if (reduction_ddr_p (pbb1
, pbb2
))
633 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
); i
++)
634 for (j
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
); j
++)
635 if (!graphite_legal_transform_dr (pbb1
, pbb2
, pdr1
, pdr2
))
641 /* Iterates over the SCOP and detect whether the transformed schedule
645 graphite_legal_transform (scop_p scop
)
648 poly_bb_p pbb1
, pbb2
;
650 timevar_push (TV_GRAPHITE_DATA_DEPS
);
652 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
653 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
654 if (!graphite_legal_transform_bb (pbb1
, pbb2
))
656 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
660 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
664 /* Remove all the dimensions except alias information at dimension
668 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset
,
669 ppl_dimension_type alias_dim
)
671 ppl_dimension_type
*ds
;
672 ppl_dimension_type access_dim
;
675 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset
,
677 ds
= XNEWVEC (ppl_dimension_type
, access_dim
-1);
678 for (i
= 0; i
< access_dim
; i
++)
687 ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset
,
693 /* Return true when PDR1 and PDR2 may alias. */
696 poly_drs_may_alias_p (poly_dr_p pdr1
, poly_dr_p pdr2
)
698 ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1
, alias_powerset2
;
699 ppl_Pointset_Powerset_C_Polyhedron_t accesses1
= PDR_ACCESSES (pdr1
);
700 ppl_Pointset_Powerset_C_Polyhedron_t accesses2
= PDR_ACCESSES (pdr2
);
701 ppl_dimension_type alias_dim1
= pdr_alias_set_dim (pdr1
);
702 ppl_dimension_type alias_dim2
= pdr_alias_set_dim (pdr2
);
705 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
706 (&alias_powerset1
, accesses1
);
707 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
708 (&alias_powerset2
, accesses2
);
710 build_alias_set_powerset (alias_powerset1
, alias_dim1
);
711 build_alias_set_powerset (alias_powerset2
, alias_dim2
);
713 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
714 (alias_powerset1
, alias_powerset2
);
716 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1
);
718 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1
);
719 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2
);
724 /* Returns TRUE when the dependence polyhedron between PDR1 and
725 PDR2 represents a loop carried dependence at level LEVEL. */
728 graphite_carried_dependence_level_k (poly_dr_p pdr1
, poly_dr_p pdr2
,
731 poly_bb_p pbb1
= PDR_PBB (pdr1
);
732 poly_bb_p pbb2
= PDR_PBB (pdr2
);
733 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
734 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
735 ppl_Polyhedron_t so1
= PBB_TRANSFORMED_SCATTERING (pbb1
);
736 ppl_Polyhedron_t so2
= PBB_TRANSFORMED_SCATTERING (pbb2
);
737 ppl_Pointset_Powerset_C_Polyhedron_t po
;
738 ppl_Pointset_Powerset_C_Polyhedron_t eqpp
;
739 graphite_dim_t tdim1
= pbb_nb_scattering_transform (pbb1
);
740 graphite_dim_t ddim1
= pbb_dim_iter_domain (pbb1
);
741 ppl_dimension_type dim
;
744 int obj_base_set1
= PDR_BASE_OBJECT_SET (pdr1
);
745 int obj_base_set2
= PDR_BASE_OBJECT_SET (pdr2
);
747 if ((pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
748 || !poly_drs_may_alias_p (pdr1
, pdr2
))
751 if (obj_base_set1
!= obj_base_set2
)
754 if (PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
))
757 pddr
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, so1
, so2
,
760 if (pddr_is_empty (pddr
))
763 po
= PDDR_DDP (pddr
);
764 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po
, &dim
);
765 eqpp
= build_pairwise_scheduling_inequality (dim
, level
, tdim1
+ ddim1
, 1);
767 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp
, po
);
768 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp
);
770 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp
);
774 /* Check data dependency between PBB1 and PBB2 at level LEVEL. */
777 dependency_between_pbbs_p (poly_bb_p pbb1
, poly_bb_p pbb2
, int level
)
780 poly_dr_p pdr1
, pdr2
;
782 timevar_push (TV_GRAPHITE_DATA_DEPS
);
784 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
); i
++)
785 for (j
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
); j
++)
786 if (graphite_carried_dependence_level_k (pdr1
, pdr2
, level
))
788 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
792 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
796 /* Pretty print to FILE all the original data dependences of SCoP in
800 dot_original_deps_stmt_1 (FILE *file
, scop_p scop
)
803 poly_bb_p pbb1
, pbb2
;
804 poly_dr_p pdr1
, pdr2
;
806 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
807 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
809 for (k
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
); k
++)
810 for (l
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
); l
++)
811 if (pddr_original_scattering (pbb1
, pbb2
, pdr1
, pdr2
))
813 fprintf (file
, "OS%d -> OS%d\n",
814 pbb_index (pbb1
), pbb_index (pbb2
));
821 /* Pretty print to FILE all the transformed data dependences of SCoP in
825 dot_transformed_deps_stmt_1 (FILE *file
, scop_p scop
)
828 poly_bb_p pbb1
, pbb2
;
829 poly_dr_p pdr1
, pdr2
;
831 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
832 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
834 for (k
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
); k
++)
835 for (l
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
); l
++)
836 if (pddr_transformed_scattering (pbb1
, pbb2
, pdr1
, pdr2
))
838 fprintf (file
, "TS%d -> TS%d\n",
839 pbb_index (pbb1
), pbb_index (pbb2
));
847 /* Pretty print to FILE all the data dependences of SCoP in DOT
851 dot_deps_stmt_1 (FILE *file
, scop_p scop
)
853 fputs ("digraph all {\n", file
);
855 dot_original_deps_stmt_1 (file
, scop
);
856 dot_transformed_deps_stmt_1 (file
, scop
);
858 fputs ("}\n\n", file
);
861 /* Pretty print to FILE all the original data dependences of SCoP in
865 dot_original_deps (FILE *file
, scop_p scop
)
868 poly_bb_p pbb1
, pbb2
;
869 poly_dr_p pdr1
, pdr2
;
871 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
872 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
873 for (k
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
); k
++)
874 for (l
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
); l
++)
875 if (pddr_original_scattering (pbb1
, pbb2
, pdr1
, pdr2
))
876 fprintf (file
, "OS%d_D%d -> OS%d_D%d\n",
877 pbb_index (pbb1
), PDR_ID (pdr1
),
878 pbb_index (pbb2
), PDR_ID (pdr2
));
881 /* Pretty print to FILE all the transformed data dependences of SCoP in
885 dot_transformed_deps (FILE *file
, scop_p scop
)
888 poly_bb_p pbb1
, pbb2
;
889 poly_dr_p pdr1
, pdr2
;
891 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
892 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
893 for (k
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
); k
++)
894 for (l
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
); l
++)
895 if (pddr_transformed_scattering (pbb1
, pbb2
, pdr1
, pdr2
))
896 fprintf (file
, "TS%d_D%d -> TS%d_D%d\n",
897 pbb_index (pbb1
), PDR_ID (pdr1
),
898 pbb_index (pbb2
), PDR_ID (pdr2
));
901 /* Pretty print to FILE all the data dependences of SCoP in DOT
905 dot_deps_1 (FILE *file
, scop_p scop
)
907 fputs ("digraph all {\n", file
);
909 dot_original_deps (file
, scop
);
910 dot_transformed_deps (file
, scop
);
912 fputs ("}\n\n", file
);
915 /* Display all the data dependences in SCoP using dotty. */
918 dot_deps (scop_p scop
)
920 /* When debugging, enable the following code. This cannot be used
921 in production compilers because it calls "system". */
924 FILE *stream
= fopen ("/tmp/scopdeps.dot", "w");
927 dot_deps_1 (stream
, scop
);
930 x
= system ("dotty /tmp/scopdeps.dot");
932 dot_deps_1 (stderr
, scop
);
936 /* Display all the statement dependences in SCoP using dotty. */
939 dot_deps_stmt (scop_p scop
)
941 /* When debugging, enable the following code. This cannot be used
942 in production compilers because it calls "system". */
945 FILE *stream
= fopen ("/tmp/scopdeps.dot", "w");
948 dot_deps_stmt_1 (stream
, scop
);
951 x
= system ("dotty /tmp/scopdeps.dot");
953 dot_deps_stmt_1 (stderr
, scop
);