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 inequality constraints: when DIRECTION is
220 1 builds a GE constraint,
221 0 builds an EQ constraint,
222 -1 builds a LE constraint. */
224 static ppl_Pointset_Powerset_C_Polyhedron_t
225 build_pairwise_scheduling (graphite_dim_t dim
,
227 graphite_dim_t offset
,
230 ppl_Pointset_Powerset_C_Polyhedron_t res
;
231 ppl_Polyhedron_t equalities
;
232 ppl_Constraint_t cstr
;
234 ppl_new_C_Polyhedron_from_space_dimension (&equalities
, dim
, 0);
239 cstr
= ppl_build_relation (dim
, pos
, pos
+ offset
, 1,
240 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
244 cstr
= ppl_build_relation (dim
, pos
, pos
+ offset
, 0,
245 PPL_CONSTRAINT_TYPE_EQUAL
);
249 cstr
= ppl_build_relation (dim
, pos
, pos
+ offset
, -1,
250 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
257 ppl_Polyhedron_add_constraint (equalities
, cstr
);
258 ppl_delete_Constraint (cstr
);
260 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res
, equalities
);
261 ppl_delete_Polyhedron (equalities
);
265 /* Returns true when adding to the RES dependence polyhedron the
266 lexicographical constraint: "DIM compared to DIM + OFFSET" returns
267 an empty polyhedron. The comparison depends on DIRECTION as: if
268 DIRECTION is equal to -1, the first dimension DIM to be compared
269 comes before the second dimension DIM + OFFSET, equal to 0 when DIM
270 and DIM + OFFSET are equal, and DIRECTION is set to 1 when DIM
271 comes after DIM + OFFSET. */
274 lexicographically_gt_p (ppl_Pointset_Powerset_C_Polyhedron_t res
,
276 graphite_dim_t offset
,
277 int direction
, graphite_dim_t i
)
279 ppl_Pointset_Powerset_C_Polyhedron_t ineq
;
282 ineq
= build_pairwise_scheduling (dim
, i
, offset
, direction
);
283 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (ineq
, res
);
284 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (ineq
);
286 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, ineq
);
287 ppl_delete_Pointset_Powerset_C_Polyhedron (ineq
);
292 /* Add to a non empty polyhedron RES the precedence constraints for
293 the lexicographical comparison of time vectors in RES following the
294 lexicographical order. DIM is the dimension of the polyhedron RES.
295 TDIM is the number of loops common to the two statements that are
296 compared lexicographically, i.e. the number of loops containing
297 both statements. OFFSET is the number of dimensions needed to
298 represent the first statement, i.e. dimT1 + dimI1 in the layout of
299 the RES polyhedron: T1|I1|T2|I2|S1|S2|G. DIRECTION is equal to 1
300 when statement 1 is after statement 2, equal to -1 when statement 1
301 is before statement 2. */
304 build_lexicographically_gt_constraint (ppl_Pointset_Powerset_C_Polyhedron_t
*res
,
307 graphite_dim_t offset
,
312 if (lexicographically_gt_p (*res
, dim
, offset
, direction
, 0))
315 for (i
= 0; i
< tdim
- 1; i
++)
317 ppl_Pointset_Powerset_C_Polyhedron_t sceq
;
319 /* All the dimensions up to I are equal, ... */
320 sceq
= build_pairwise_scheduling (dim
, i
, offset
, 0);
321 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res
, sceq
);
322 ppl_delete_Pointset_Powerset_C_Polyhedron (sceq
);
324 /* ... and at depth I+1 they are not equal anymore. */
325 if (lexicographically_gt_p (*res
, dim
, offset
, direction
, i
+ 1))
331 ppl_delete_Pointset_Powerset_C_Polyhedron (*res
);
332 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (res
, dim
, 1);
336 /* Build the dependence polyhedron for data references PDR1 and PDR2.
337 The layout of the dependence polyhedron is:
342 | T1 and T2 the scattering dimensions for PDR1 and PDR2
343 | I1 and I2 the iteration domains
344 | S1 and S2 the subscripts
345 | G the global parameters.
347 D1 and D2 are the iteration domains of PDR1 and PDR2.
349 SCAT1 and SCAT2 are the scattering polyhedra for PDR1 and PDR2.
350 When ORIGINAL_SCATTERING_P is true, then the scattering polyhedra
351 SCAT1 and SCAT2 correspond to the original scattering of the
352 program, otherwise they correspond to the transformed scattering.
354 DIRECTION is equal to 1 when statement 1 is after statement 2,
355 equal to -1 when statement 1 is before statement 2. */
358 dependence_polyhedron_1 (poly_bb_p pbb1
, poly_bb_p pbb2
,
359 ppl_Pointset_Powerset_C_Polyhedron_t d1
,
360 ppl_Pointset_Powerset_C_Polyhedron_t d2
,
361 poly_dr_p pdr1
, poly_dr_p pdr2
,
362 ppl_Polyhedron_t scat1
, ppl_Polyhedron_t scat2
,
364 bool original_scattering_p
)
366 scop_p scop
= PBB_SCOP (pbb1
);
367 graphite_dim_t tdim1
= original_scattering_p
?
368 pbb_nb_scattering_orig (pbb1
) : pbb_nb_scattering_transform (pbb1
);
369 graphite_dim_t tdim2
= original_scattering_p
?
370 pbb_nb_scattering_orig (pbb2
) : pbb_nb_scattering_transform (pbb2
);
371 graphite_dim_t ddim1
= pbb_dim_iter_domain (pbb1
);
372 graphite_dim_t ddim2
= pbb_dim_iter_domain (pbb2
);
373 graphite_dim_t sdim1
= PDR_NB_SUBSCRIPTS (pdr1
) + 1;
374 graphite_dim_t gdim
= scop_nb_params (scop
);
375 graphite_dim_t dim1
= pdr_dim (pdr1
);
376 graphite_dim_t dim2
= pdr_dim (pdr2
);
377 graphite_dim_t dim
= tdim1
+ tdim2
+ dim1
+ dim2
- gdim
;
378 ppl_Pointset_Powerset_C_Polyhedron_t res
;
379 ppl_Pointset_Powerset_C_Polyhedron_t id1
, id2
, isc1
, isc2
, idr1
, idr2
;
380 ppl_Pointset_Powerset_C_Polyhedron_t sc1
, sc2
, dreq
;
381 ppl_Pointset_Powerset_C_Polyhedron_t context
;
383 gcc_assert (PBB_SCOP (pbb1
) == PBB_SCOP (pbb2
));
385 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
386 (&context
, SCOP_CONTEXT (scop
));
387 ppl_insert_dimensions_pointset (context
, 0, dim
- gdim
);
389 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc1
, scat1
);
390 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc2
, scat2
);
392 id1
= map_into_dep_poly (dim
, gdim
, d1
, ddim1
, tdim1
);
393 id2
= map_into_dep_poly (dim
, gdim
, d2
, ddim2
, tdim1
+ ddim1
+ tdim2
);
394 isc1
= map_into_dep_poly (dim
, gdim
, sc1
, ddim1
+ tdim1
, 0);
395 isc2
= map_into_dep_poly (dim
, gdim
, sc2
, ddim2
+ tdim2
, tdim1
+ ddim1
);
397 idr1
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr1
), ddim1
, ddim1
+ gdim
,
398 tdim1
, tdim2
+ ddim2
);
399 idr2
= map_dr_into_dep_poly (dim
, PDR_ACCESSES (pdr2
), ddim2
, ddim2
+ gdim
,
400 tdim1
+ ddim1
+ tdim2
, sdim1
);
402 /* Now add the subscript equalities. */
403 dreq
= dr_equality_constraints (dim
, tdim1
+ ddim1
+ tdim2
+ ddim2
, sdim1
);
405 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res
, dim
, 0);
406 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, context
);
407 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, id1
);
408 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, id2
);
409 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, isc1
);
410 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, isc2
);
411 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr1
);
412 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, idr2
);
413 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res
, dreq
);
414 ppl_delete_Pointset_Powerset_C_Polyhedron (context
);
415 ppl_delete_Pointset_Powerset_C_Polyhedron (id1
);
416 ppl_delete_Pointset_Powerset_C_Polyhedron (id2
);
417 ppl_delete_Pointset_Powerset_C_Polyhedron (sc1
);
418 ppl_delete_Pointset_Powerset_C_Polyhedron (sc2
);
419 ppl_delete_Pointset_Powerset_C_Polyhedron (isc1
);
420 ppl_delete_Pointset_Powerset_C_Polyhedron (isc2
);
421 ppl_delete_Pointset_Powerset_C_Polyhedron (idr1
);
422 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2
);
423 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq
);
425 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res
))
426 build_lexicographically_gt_constraint (&res
, dim
, MIN (tdim1
, tdim2
),
427 tdim1
+ ddim1
, direction
);
429 return new_poly_ddr (pdr1
, pdr2
, res
);
432 /* Build the dependence polyhedron for data references PDR1 and PDR2.
433 If possible use already cached information.
435 D1 and D2 are the iteration domains of PDR1 and PDR2.
437 SCAT1 and SCAT2 are the scattering polyhedra for PDR1 and PDR2.
438 When ORIGINAL_SCATTERING_P is true, then the scattering polyhedra
439 SCAT1 and SCAT2 correspond to the original scattering of the
440 program, otherwise they correspond to the transformed scattering.
442 DIRECTION is equal to 1 when statement 1 is after statement 2,
443 equal to -1 when statement 1 is before statement 2. */
446 dependence_polyhedron (poly_bb_p pbb1
, poly_bb_p pbb2
,
447 ppl_Pointset_Powerset_C_Polyhedron_t d1
,
448 ppl_Pointset_Powerset_C_Polyhedron_t d2
,
449 poly_dr_p pdr1
, poly_dr_p pdr2
,
450 ppl_Polyhedron_t scat1
, ppl_Polyhedron_t scat2
,
452 bool original_scattering_p
)
457 if (original_scattering_p
)
463 x
= htab_find_slot (SCOP_ORIGINAL_PDDRS (PBB_SCOP (pbb1
)),
467 return (poly_ddr_p
) *x
;
470 res
= dependence_polyhedron_1 (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
,
471 scat1
, scat2
, direction
, original_scattering_p
);
473 if (original_scattering_p
)
479 /* Returns the Polyhedral Data Dependence Relation (PDDR) between PDR1
480 contained in PBB1 and PDR2 contained in PBB2. When
481 ORIGINAL_SCATTERING_P is true, return the PDDR corresponding to the
482 original scattering, or NULL if the dependence relation is empty.
483 When ORIGINAL_SCATTERING_P is false, return the PDDR corresponding
484 to the transformed scattering. */
487 build_pddr (poly_bb_p pbb1
, poly_bb_p pbb2
, poly_dr_p pdr1
, poly_dr_p pdr2
,
488 bool original_scattering_p
)
491 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
492 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
493 ppl_Polyhedron_t scat1
= original_scattering_p
?
494 PBB_ORIGINAL_SCATTERING (pbb1
) : PBB_TRANSFORMED_SCATTERING (pbb1
);
495 ppl_Polyhedron_t scat2
= original_scattering_p
?
496 PBB_ORIGINAL_SCATTERING (pbb2
) : PBB_TRANSFORMED_SCATTERING (pbb2
);
498 if ((pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
499 || PDR_BASE_OBJECT_SET (pdr1
) != PDR_BASE_OBJECT_SET (pdr2
)
500 || PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
))
503 pddr
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, scat1
, scat2
,
504 1, original_scattering_p
);
505 if (pddr_is_empty (pddr
))
511 /* Return true when the data dependence relation between the data
512 references PDR1 belonging to PBB1 and PDR2 is part of a
516 reduction_dr_1 (poly_bb_p pbb1
, poly_dr_p pdr1
, poly_dr_p pdr2
)
521 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr
); i
++)
522 if (PDR_TYPE (pdr
) == PDR_WRITE
)
525 return same_pdr_p (pdr
, pdr1
) && same_pdr_p (pdr
, pdr2
);
528 /* Return true when the data dependence relation between the data
529 references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
530 part of a reduction. */
533 reduction_dr_p (poly_bb_p pbb1
, poly_bb_p pbb2
,
534 poly_dr_p pdr1
, poly_dr_p pdr2
)
536 if (PBB_IS_REDUCTION (pbb1
))
537 return reduction_dr_1 (pbb1
, pdr1
, pdr2
);
539 if (PBB_IS_REDUCTION (pbb2
))
540 return reduction_dr_1 (pbb2
, pdr2
, pdr1
);
545 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
546 and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
550 graphite_legal_transform_dr (poly_bb_p pbb1
, poly_bb_p pbb2
,
551 poly_dr_p pdr1
, poly_dr_p pdr2
)
553 ppl_Polyhedron_t st1
, st2
;
554 ppl_Pointset_Powerset_C_Polyhedron_t po
, pt
;
555 graphite_dim_t ddim1
, otdim1
, otdim2
, ttdim1
, ttdim2
;
556 ppl_Pointset_Powerset_C_Polyhedron_t temp
;
557 ppl_dimension_type pdim
;
560 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
561 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
563 if (reduction_dr_p (pbb1
, pbb2
, pdr1
, pdr2
))
566 pddr
= build_pddr (pbb1
, pbb2
, pdr1
, pdr2
, true);
570 po
= PDDR_DDP (pddr
);
572 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
573 fprintf (dump_file
, "\nloop carries dependency.\n");
575 st1
= PBB_TRANSFORMED_SCATTERING (pbb1
);
576 st2
= PBB_TRANSFORMED_SCATTERING (pbb2
);
577 ddim1
= pbb_dim_iter_domain (pbb1
);
578 otdim1
= pbb_nb_scattering_orig (pbb1
);
579 otdim2
= pbb_nb_scattering_orig (pbb2
);
580 ttdim1
= pbb_nb_scattering_transform (pbb1
);
581 ttdim2
= pbb_nb_scattering_transform (pbb2
);
583 /* Copy the PO polyhedron into the TEMP, so it is not destroyed.
584 Keep in mind, that PO polyhedron might be restored from the cache
585 and should not be modified! */
586 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po
, &pdim
);
587 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&temp
, pdim
, 0);
588 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp
, po
);
590 pddr
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, st1
, st2
,
592 pt
= PDDR_DDP (pddr
);
594 /* Extend PO and PT to have the same dimensions. */
595 ppl_insert_dimensions_pointset (temp
, otdim1
, ttdim1
);
596 ppl_insert_dimensions_pointset (temp
, otdim1
+ ttdim1
+ ddim1
+ otdim2
, ttdim2
);
597 ppl_insert_dimensions_pointset (pt
, 0, otdim1
);
598 ppl_insert_dimensions_pointset (pt
, otdim1
+ ttdim1
+ ddim1
, otdim2
);
600 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp
, pt
);
601 is_empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp
);
603 ppl_delete_Pointset_Powerset_C_Polyhedron (temp
);
604 free_poly_ddr (pddr
);
609 /* Return true when the data dependence relation for PBB1 and PBB2 is
610 part of a reduction. */
613 reduction_ddr_p (poly_bb_p pbb1
, poly_bb_p pbb2
)
615 return pbb1
== pbb2
&& PBB_IS_REDUCTION (pbb1
);
618 /* Iterates over the data references of PBB1 and PBB2 and detect
619 whether the transformed schedule is correct. */
622 graphite_legal_transform_bb (poly_bb_p pbb1
, poly_bb_p pbb2
)
625 poly_dr_p pdr1
, pdr2
;
627 if (!PBB_PDR_DUPLICATES_REMOVED (pbb1
))
628 pbb_remove_duplicate_pdrs (pbb1
);
630 if (!PBB_PDR_DUPLICATES_REMOVED (pbb2
))
631 pbb_remove_duplicate_pdrs (pbb2
);
633 if (reduction_ddr_p (pbb1
, pbb2
))
636 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
); i
++)
637 for (j
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
); j
++)
638 if (!graphite_legal_transform_dr (pbb1
, pbb2
, pdr1
, pdr2
))
644 /* Iterates over the SCOP and detect whether the transformed schedule
648 graphite_legal_transform (scop_p scop
)
651 poly_bb_p pbb1
, pbb2
;
653 timevar_push (TV_GRAPHITE_DATA_DEPS
);
655 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
656 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
657 if (!graphite_legal_transform_bb (pbb1
, pbb2
))
659 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
663 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
667 /* Remove all the dimensions except alias information at dimension
671 build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset
,
672 ppl_dimension_type alias_dim
)
674 ppl_dimension_type
*ds
;
675 ppl_dimension_type access_dim
;
678 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset
,
680 ds
= XNEWVEC (ppl_dimension_type
, access_dim
-1);
681 for (i
= 0; i
< access_dim
; i
++)
690 ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset
,
696 /* Return true when PDR1 and PDR2 may alias. */
699 poly_drs_may_alias_p (poly_dr_p pdr1
, poly_dr_p pdr2
)
701 ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1
, alias_powerset2
;
702 ppl_Pointset_Powerset_C_Polyhedron_t accesses1
= PDR_ACCESSES (pdr1
);
703 ppl_Pointset_Powerset_C_Polyhedron_t accesses2
= PDR_ACCESSES (pdr2
);
704 ppl_dimension_type alias_dim1
= pdr_alias_set_dim (pdr1
);
705 ppl_dimension_type alias_dim2
= pdr_alias_set_dim (pdr2
);
708 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
709 (&alias_powerset1
, accesses1
);
710 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
711 (&alias_powerset2
, accesses2
);
713 build_alias_set_powerset (alias_powerset1
, alias_dim1
);
714 build_alias_set_powerset (alias_powerset2
, alias_dim2
);
716 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
717 (alias_powerset1
, alias_powerset2
);
719 empty_p
= ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1
);
721 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1
);
722 ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2
);
727 /* Returns TRUE when the dependence polyhedron between PDR1 and
728 PDR2 represents a loop carried dependence at level LEVEL. */
731 graphite_carried_dependence_level_k (poly_dr_p pdr1
, poly_dr_p pdr2
,
734 poly_bb_p pbb1
= PDR_PBB (pdr1
);
735 poly_bb_p pbb2
= PDR_PBB (pdr2
);
736 ppl_Pointset_Powerset_C_Polyhedron_t d1
= PBB_DOMAIN (pbb1
);
737 ppl_Pointset_Powerset_C_Polyhedron_t d2
= PBB_DOMAIN (pbb2
);
738 ppl_Polyhedron_t so1
= PBB_TRANSFORMED_SCATTERING (pbb1
);
739 ppl_Polyhedron_t so2
= PBB_TRANSFORMED_SCATTERING (pbb2
);
740 ppl_Pointset_Powerset_C_Polyhedron_t po
;
741 ppl_Pointset_Powerset_C_Polyhedron_t eqpp
;
742 graphite_dim_t tdim1
= pbb_nb_scattering_transform (pbb1
);
743 graphite_dim_t ddim1
= pbb_dim_iter_domain (pbb1
);
744 ppl_dimension_type dim
;
747 int obj_base_set1
= PDR_BASE_OBJECT_SET (pdr1
);
748 int obj_base_set2
= PDR_BASE_OBJECT_SET (pdr2
);
750 if ((pdr_read_p (pdr1
) && pdr_read_p (pdr2
))
751 || !poly_drs_may_alias_p (pdr1
, pdr2
))
754 if (obj_base_set1
!= obj_base_set2
)
757 if (PDR_NB_SUBSCRIPTS (pdr1
) != PDR_NB_SUBSCRIPTS (pdr2
))
760 pddr
= dependence_polyhedron (pbb1
, pbb2
, d1
, d2
, pdr1
, pdr2
, so1
, so2
,
763 if (pddr_is_empty (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_Pointset_Powerset_C_Polyhedron_is_empty (eqpp
);
773 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp
);
777 /* Check data dependency between PBB1 and PBB2 at level LEVEL. */
780 dependency_between_pbbs_p (poly_bb_p pbb1
, poly_bb_p pbb2
, int level
)
783 poly_dr_p pdr1
, pdr2
;
785 timevar_push (TV_GRAPHITE_DATA_DEPS
);
787 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), i
, pdr1
); i
++)
788 for (j
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), j
, pdr2
); j
++)
789 if (graphite_carried_dependence_level_k (pdr1
, pdr2
, level
))
791 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
795 timevar_pop (TV_GRAPHITE_DATA_DEPS
);
799 /* Pretty print to FILE all the original data dependences of SCoP in
803 dot_original_deps_stmt_1 (FILE *file
, scop_p scop
)
806 poly_bb_p pbb1
, pbb2
;
807 poly_dr_p pdr1
, pdr2
;
809 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
810 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
812 for (k
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
); k
++)
813 for (l
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
); l
++)
814 if (build_pddr (pbb1
, pbb2
, pdr1
, pdr2
, true))
816 fprintf (file
, "OS%d -> OS%d\n",
817 pbb_index (pbb1
), pbb_index (pbb2
));
824 /* Pretty print to FILE all the transformed data dependences of SCoP in
828 dot_transformed_deps_stmt_1 (FILE *file
, scop_p scop
)
831 poly_bb_p pbb1
, pbb2
;
832 poly_dr_p pdr1
, pdr2
;
835 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
836 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
838 for (k
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
); k
++)
839 for (l
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
); l
++)
840 if ((pddr
= build_pddr (pbb1
, pbb2
, pdr1
, pdr2
, false)))
842 fprintf (file
, "TS%d -> TS%d\n",
843 pbb_index (pbb1
), pbb_index (pbb2
));
844 free_poly_ddr (pddr
);
852 /* Pretty print to FILE all the data dependences of SCoP in DOT
856 dot_deps_stmt_1 (FILE *file
, scop_p scop
)
858 fputs ("digraph all {\n", file
);
860 dot_original_deps_stmt_1 (file
, scop
);
861 dot_transformed_deps_stmt_1 (file
, scop
);
863 fputs ("}\n\n", file
);
866 /* Pretty print to FILE all the original data dependences of SCoP in
870 dot_original_deps (FILE *file
, scop_p scop
)
873 poly_bb_p pbb1
, pbb2
;
874 poly_dr_p pdr1
, pdr2
;
876 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
877 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
878 for (k
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
); k
++)
879 for (l
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
); l
++)
880 if (build_pddr (pbb1
, pbb2
, pdr1
, pdr2
, true))
881 fprintf (file
, "OS%d_D%d -> OS%d_D%d\n",
882 pbb_index (pbb1
), PDR_ID (pdr1
),
883 pbb_index (pbb2
), PDR_ID (pdr2
));
886 /* Pretty print to FILE all the transformed data dependences of SCoP in
890 dot_transformed_deps (FILE *file
, scop_p scop
)
893 poly_bb_p pbb1
, pbb2
;
894 poly_dr_p pdr1
, pdr2
;
897 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb1
); i
++)
898 for (j
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), j
, pbb2
); j
++)
899 for (k
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb1
), k
, pdr1
); k
++)
900 for (l
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb2
), l
, pdr2
); l
++)
901 if ((pddr
= build_pddr (pbb1
, pbb2
, pdr1
, pdr2
, false)))
903 fprintf (file
, "TS%d_D%d -> TS%d_D%d\n",
904 pbb_index (pbb1
), PDR_ID (pdr1
),
905 pbb_index (pbb2
), PDR_ID (pdr2
));
906 free_poly_ddr (pddr
);
910 /* Pretty print to FILE all the data dependences of SCoP in DOT
914 dot_deps_1 (FILE *file
, scop_p scop
)
916 fputs ("digraph all {\n", file
);
918 dot_original_deps (file
, scop
);
919 dot_transformed_deps (file
, scop
);
921 fputs ("}\n\n", file
);
924 /* Display all the data dependences in SCoP using dotty. */
927 dot_deps (scop_p scop
)
929 /* When debugging, enable the following code. This cannot be used
930 in production compilers because it calls "system". */
933 FILE *stream
= fopen ("/tmp/scopdeps.dot", "w");
936 dot_deps_1 (stream
, scop
);
939 x
= system ("dotty /tmp/scopdeps.dot");
941 dot_deps_1 (stderr
, scop
);
945 /* Display all the statement dependences in SCoP using dotty. */
948 dot_deps_stmt (scop_p scop
)
950 /* When debugging, enable the following code. This cannot be used
951 in production compilers because it calls "system". */
954 FILE *stream
= fopen ("/tmp/scopdeps.dot", "w");
957 dot_deps_stmt_1 (stream
, scop
);
960 x
= system ("dotty /tmp/scopdeps.dot");
962 dot_deps_stmt_1 (stderr
, scop
);